### [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 thoughts on “[ERRONEOUS] A proof of P=NP using a Merkle tree – a new version”

1. Tracy says:

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

2. porton says:

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

3. porton says:

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.