Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets
Authors: Hartmanis, Juris
Hemachandra, Lane A.
Keywords: computer science
technical report
Issue Date: Jan-1986
Publisher: Cornell University
Abstract: This paper 1. gives a relativized counterexample to the conjectured connection between the existence of one-way functions and the existence of non-isomorphic NP-complete sets. 2. establishes that in relativized worlds there are NP-complete sets that are non-isomorphic in a strong sense. 3. proves that robust machines squander their powerful nondeterministic oracle access in all relativizations. (1) resolves an open question. (2) extends our knowledge about non-isomorphic NP-complete sets. (3) sharing the proof techniques of (1) and (2), enriches the nascent theory of robustness and presents a consequence of the limited combinatorial control of machines.
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
86-796.pdf1.73 MBAdobe PDFView/Open
86-796.ps445.92 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us