On Non-Isomorphic NP Complete Sets
Permanent Link(s)
Collections
Author
Hartmanis, Juris
Abstract
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.
Date Issued
1983-10
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-576
Type
technical report