Inverting Onto Functions

Here's an open question that goes back to a 2003 paper  that I wrote with Steve Fenner, John Rogers and Ashish Naik. The conference paper goes back to 1996.

In that paper we discuss two hypothesis we badly called Q and Q' and it still remains open whether the two hypotheses are equivalent.

Q has a number of equivalent definitions, including

• For all NP machines M that accepting all strings, there is polynomial-time computable function f such that f(x) is an accepting path of M(x) for all x.
• For every onto honest polynomial-time computable function g there is a polynomial-time computable function f such that f finds an inverse of g, more precisely g(f(g(x))) = g(x) for all x.
• TFNP is computable in FP.

For lots more equivalences see the paper. 

Q' is the bit version of Q. For example

• For all NP machines M that accepting all strings, there is polynomial-time computable function f such that f(x) outputs the first bit of an accepting path of M(x) for all x.
• For every onto honest polynomial-time computable function g there is a polynomial-time computable function f such that f finds the first bit of an inverse of g, more precisely for all x there is a y such that g(y) = g(x) and f(x) is the first bit of y.

Now Q implies Q', if you can find an accepting path of M(x) you can just read off the first bit. Does Q' imply Q? 

If P = NP you can find solutions using self-reductions. For Q' self-reduction gets stuck because as you start filling in bits you may lose the "onto" promise. 

On the other hand we don't even know any relativized worlds where Q' is true and Q is false. So either prove that Q' implies Q or show a relativized world where Q' is true and Q is false.

How often can I dole out 22-year old open problems that don't require deep complexity to understand. Can't promise what techniques you'll need to solve it.

Computational Complexity published first on Computational Complexity