On Non-Isomorphic NP Complete Sets
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.
computer science; technical report
Previously Published As