One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets

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.