Portal de Periódicos da CAPES

Inverting onto functions

2003; Elsevier BV; Volume: 186; Issue: 1 Linguagem: Inglês

10.1016/s0890-5401(03)00119-6

1090-2651

Stephen Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers,

Cryptography and Data Security

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: In polynomial time, one can find accepting paths of nondeterministic polynomial-time Turing machines that accept Σ*. Every total multivalued nondeterministic function has a polynomial-time computable refinement. In polynomial time, one can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. In polynomial time, one can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments.