8
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.