Skip to main content


eCommons@Cornell

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

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6636
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
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-796
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.
URI: http://hdl.handle.net/1813/6636
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