What is wrong with this proof that P≠NP?

Question

Proof by contradiction:

Assume that $P=NP$.

There must exist a function that maps from NP to P.

So there must exist a function $T$ that, given the source code of a polynomial-time verifier function $V$ (which is a representation of the problem in $NP$), can compute the corresponding polynomial-time solution-finder function $S$ (which is a representation of the problem in $P$).

So $S = T(V)$ and $V(x, S(x))$ is true for all valid $x$.

Construct $V_1$ like this:

V_1(x, y) {
    // x: input
    // y: solution to be verified

    S_1 = T(V_1); // this step runs in constant time
    if( S_1(x) == y ) return 'wrong'; // this step runs in polynomial time
    else return 'correct';
}

$V_1$ runs in polynomial time (of the length of $x$) because the $S_1 = T(V_1)$ step runs in constant time and $S_1(x)$ runs in polynomial time (of the length of $x$).

Since $V_1$ is a polynomial-time verifier, the $S_1$ produced by $T(V_1)$ should always be able to find a solution $V_1$ verifies as correct. But with our $V_1$, the solution $S_1$ finds for any input will always be wrong.

This is a contradiction. So no function $T$ that can compute the polynomial-time solution finder given the polynomial-time verifier exists.

So no function can connect $NP$ to $P$.

So $P≠NP$.

---

Is the logic that there must exist a function $T$ that 'connect' $NP$ to $P$ flawed?

Or maybe $T$ exists but doesn't run in finite time?

Answer 1

As far as I know there might be multiple solutions certifying solvability of NP problem. For most of NP complex problems, the function T that searches all the solution space and verifies it by V would be fine, but running in exponentional time due to the number of possible inputs.

Provided NP=P it would be sufficient to find an polynomial algorithm that for given problem tells if there is one certificating instance that solves it. However you would not break into much treasuries using that algorithm.

The other question would be if there must be polynomial algorithm to find the certification. And even if it would be the case, it still does not as far as I know mean that it will be a polynomial function of certificating function.

Going further you constructed the problem for which you know that there exist no pair $V_1$, $S_1$ that would solve it. So if your T is clever enough it will print the output "there is no such S to solve this recursive ill posed problem":)