Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On Non-Isomorphic NP Complete Sets

On Non-Isomorphic NP Complete Sets

File(s)
83-576.pdf (415.63 KB)
83-576.ps (164.11 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6416
Collections
Computer Science Technical Reports
Hartmanis, Juris
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
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-576
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance