Let $L$ be an NP complete language. My loose intuition for completeness suggests that, at any point in a computation tableau for $L$, either the computation has "already done an NP complete amount of work" or else it "has an NP complete amount of work left to go."
To formalize this intuition, we can imagine a function $f(x)$ representing the information gathered at an intermediate point in the computation on input $x$, and then say that either computing $f$ is NP complete, or else $L$ remains NP complete even when $f(x)$ is provided as a helpful extra part of the input. More concretely:
Conjecture: Let $f$ be any function such that, on input $(x, y)$, one can check whether $f(x) = y$ in polynomial time. Then one of the following holds:
- Computing $f(x)$ is FNP complete, or
- The following language $L'$ is NP complete: an input $(x, y)$ is a YES instance for $L'$ if $f(x)=y$ and also $x$ is a YES instance for $L$; otherwise $(x, y)$ is a NO instance for $x'$.
Is this known to be true or false? I would also be interested if it were known to be true or false in a certain relativized world.