Title :
Inverting onto functions
Author :
Fenner, Stephen A. ; Fortnow, Lance ; Naik, Ashish V. ; Rogers, John D.
Author_Institution :
Dept. of Comput. Sci., Univ. of Southern Maine, Portland, ME, USA
Abstract :
We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity conjectures including: One can find accepting paths of nondeterministic polynomial-time Turing machines that accept Σ*. Every total multivalued nondeterministic function has a polynomial-time computable refinement. One can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. One can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments. We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse, path, etc
Keywords :
Turing machines; computational complexity; SAT; Turing machines; complexity; complexity conjectures; multivalued nondeterministic function; polynomial-time computable; Complexity theory; Computer science; Polynomials; Robustness; Telecommunications; Turing machines;
Conference_Titel :
Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
Conference_Location :
Philadelphia, PA
Print_ISBN :
0-8186-7386-9
DOI :
10.1109/CCC.1996.507683