On Non-Isomorphic NP Complete Sets
Juris Hartmanis · eCommons (Cornell University) · 1983
In this note we show that if the satisfiability of Boolean formulas of low Kolmogorov complexity can be determined in polynomial-time then there exist NP complete sets that are not polynomial-time isomorphic. Keywords: NP complete sets, isomorphism, Kolmogorov complexity.