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:
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”
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.