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.

### Like this:

Like Loading...

*Related*

An amazing, well articulated article by a great Mathematician VICTOR PORTON.

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).

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.