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|
|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|
Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.