Check my proof of P=NP for errors [pdf]
github.com
Check my proof of P=NP for errors [pdf]
1–10 of 13 posts
Re: Check my proof of P=NP for errors [pdf]
#2I prove that an NP-complete cryptocurrency is polynomial time. Comment if you did or did not found an error. No efficient algorithm found.
Re: Check my proof of P=NP for errors [pdf]
#3Well that's certainly an attention grabbing headline.
Given the content of the paper as well as the list of references, I suspect this is just a clever ad for Cartesi, which is some kind of cryptocurrency apparently.
Re: Check my proof of P=NP for errors [pdf]
#4Well that's certainly an attention grabbing headline. Given the content of the paper as well as the list of references, I suspect this is just a clever ad for Cartesi, which is some kind of cryptocurrency apparently.
I am not an employee or partner of Cartesi (however, in the future I am going to be), I even tried to be hired but wasn't. I do like Cartesi to be advertised because I like that OSS project, but not so much to spend my time in marketing them. So, no, I don't advertise them by my P=NP question.
Re: Check my proof of P=NP for errors [pdf]
#5> Assume P != NP for hashes to work.
Why?
Isn't brute forcing non-broken cryptographic hash function EXPTIME complexity class? (relative to output size bits).
Even if P=NP cryptographic hashes should work just fine.
Re: Check my proof of P=NP for errors [pdf]
#6> Assume P != NP for hashes to work. Why? Isn't brute forcing non-broken cryptographic hash function EXPTIME complexity class? (relative to output size bits). Even if P=NP cryptographic hashes should work just fine.
Because for my proof to work I need polynomial-time hashing.
Re: Check my proof of P=NP for errors [pdf]
#7I'm not really clear about what you're describing, but a few thoughts...
log(t(A, X)) * log(t(A, X)) is log(t)^2, not 2log(t).
Not sure if "split memory not by halves but by interleaving fragments" is crucial, but splitting by anything other than halves leads to complexity > log2. The more unbalanced the splits, the worse the complexity. The upper bound is O(n).
It seems you're proposing the creation of a (merkel) tree which maps algorithm A's domain (inputs) to its co-domain (outputs), and then inverting that tree to map the co-domain to the domain. If that's the case, the problem is that creating just the initial tree is O(2^n); I think this is implied when you specified "infinite memory". Then you have further operations to invert. Once you have the inverted tree, any particular lookup is indeed O(log n), but you have to amoritize the initial setup, and you wind up with O([k * 2^n] + log(n)), where k is 1/number-of-lookups-performed.
Re: Check my proof of P=NP for errors [pdf]
#8I'm not really clear about what you're describing, but a few thoughts... log(t(A, X)) * log(t(A, X)) is log(t)^2, not 2log(t). Not sure if "split memory not by halves but by interleaving fragments" is crucial, but splitting by anything other than halves leads to complexity > log2. The more unbalanced the splits, the worse the complexity. The upper bound is O(n). It seems you're proposing the creation of a (merkel) tr…
You understood mostly right, but see my another comment for more detailed proof that does address this issue by ignoring zero-filled fragments of INFINITE memory.
There is no "n".
Re: Check my proof of P=NP for errors [pdf]
#9More detailed proof of P=NP with errors corrected:
https://math.portonvictor.org/wp-content/uploads/2021/06/pnp...
Re: Check my proof of P=NP for errors [pdf]
#10I'm not really clear about what you're describing, but a few thoughts... log(t(A, X)) * log(t(A, X)) is log(t)^2, not 2log(t). Not sure if "split memory not by halves but by interleaving fragments" is crucial, but splitting by anything other than halves leads to complexity > log2. The more unbalanced the splits, the worse the complexity. The upper bound is O(n). It seems you're proposing the creation of a (merkel) tr…
You understood mostly right, but see my another comment for more detailed proof that does address this issue by ignoring zero-filled fragments of INFINITE memory. There is no "n".