principleModerate
What is wrong with this conditional proof of P=NP?
Viewed 0 times
thiswhatwithconditionalwrongproof
Problem
I have recently thought up the following proof that L=P implies P=NP.
Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL. But then NL is contained in P, which means that NP is contained in P and therefore P=NP.
By the efficient market hypothesis, I suspect this proof is flawed. I am however unable to determine the exact nature of the error. Can someone point it out?
Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL. But then NL is contained in P, which means that NP is contained in P and therefore P=NP.
By the efficient market hypothesis, I suspect this proof is flawed. I am however unable to determine the exact nature of the error. Can someone point it out?
Solution
Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL.
You haven't shown that NP$\,=\,$NL. The only method you've derived to show that $x\in A$, is to nondeterministically "guess" a witness $y$ and use the deterministic logspace algorithm to verify it. However, $y$ itself may be polynomially long, whereas your NL machine can only guess logarithmically many bits: your NL machine doesn't have enough space to store the witness, so you don't have an NL algorithm.
Also, note that we already know that witnesses to NP-complete problems can be verified in a complexity class smaller than L. Fagin's theorem says that NP is exactly the set of problems that can be defined in the existential fragment of second-order logic. This is equivalent to saying that you can verify a polynomial-length witness using first-order logic. FO is strictly weaker than L, since first-order logic can't solve simple logspace problems like telling you if your witness string contains an even number of $1$s.
You haven't shown that NP$\,=\,$NL. The only method you've derived to show that $x\in A$, is to nondeterministically "guess" a witness $y$ and use the deterministic logspace algorithm to verify it. However, $y$ itself may be polynomially long, whereas your NL machine can only guess logarithmically many bits: your NL machine doesn't have enough space to store the witness, so you don't have an NL algorithm.
Also, note that we already know that witnesses to NP-complete problems can be verified in a complexity class smaller than L. Fagin's theorem says that NP is exactly the set of problems that can be defined in the existential fragment of second-order logic. This is equivalent to saying that you can verify a polynomial-length witness using first-order logic. FO is strictly weaker than L, since first-order logic can't solve simple logspace problems like telling you if your witness string contains an even number of $1$s.
Context
StackExchange Computer Science Q#72650, answer score: 11
Revisions (0)
No revisions yet.