[ERRONEOUS] A proof of P=NP using a Merkle tree – a new version

I’ve produced a short and much elementary proof of P=NP (without an efficient algorithm presented). I sent it to a reputable CS journal and insofar there were no errors noticed by the editor.

Here is an updated version of my proof with some errors corrected:

p=np-merkle.pdf

In more details (and some errors corrected):

Yet a small error corrected:

Changed execution model to have “disk” to verify input/output:

Yet error corrected:

Report if you found any errors in comments.

I also sent it to developers of automatic proof verification softwares.

3 comments

  1. I did a logic error: I by mistake assumed that every verifier of an NP-compete problem is polynomial-time.

    I proved an important (new?) result: Every at-most exponential-time algorithm can be verified in polynomial time. That will be useful for Cartesi blockchain (I informed them).

  2. One more small proof step:

    – Every EXPTIME problem f can be verified by an algorithm v solving an NP-complete problem: f(x) = 1 <=> v(x, a) = 1.
    – In turn, v can be verified by a polynomial-time algorithm u: v(x, a) = 1 <=> u(x, a, b) = 1.
    – So, the original EXPTIME can be verified by polynomial-time algorithm u using data (a, b).
    – EXPTIME = NP.

Leave a Reply