3 ms·

Check my proof of P=NP for errors [pdf]

3 points by porton 5y ago

porton 5y ago
I prove that an NP-complete cryptocurrency is polynomial time. Comment if you did or did not found an error. No efficient algorithm found.
metalliqaz 5y ago
Well 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.
- porton 5y ago
  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.
nabla9 5y ago
> 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.
- porton 5y ago
  Because for my proof to work I need polynomial-time hashing.
mgsouth 5y ago
I'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.
- porton 5y ago
  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".
  - porton 5y ago
    Well, https://math.portonvictor.org/wp-content/uploads/2021/06/pnp-merkle-4.pdf https://math.portonvictor.org/wp-content/uploads/2021/06/pnp...
  - mgsouth 5y ago
    "n" is the number of bits (what you referred to as "X"). Storing one value into a tree is O(log(X)). However, storing all possible values for X bits is 2^X operations, each of which requires log(X) sub-operations to store it. Pre-calculating all possible input-output mappings requires looking at every possible input value. Thats 2^X. That isn't what P =? NP is looking for. The forward function, A, isn't a big look-up table. Instead, it's a much smaller set of transformational steps. So if A(y) is defined as y+1, you can code it with about X primitive logical operations. One operation could be "output[least significant bit] = xor(input[least significant bit], 1)". That operation causes a transformation to every single input value, and is thus very powerful and economical. Other operations would ripple the carry to the more significant bits; the next-to-least-significant operation transforms half of the input values, the next bit affects one quarter of them, and so on. P =? NP asks if it's always possible to come up with a reasonably small set of transformations that go the opposite way. You can't do that with a process that looks at the discrete values. If it's possible it will require some kind of comprehension of the algorithm's structure. We can't (in polynomial time) create an inverse of "y+1" by listing what happens for each possible input value. We need to recognize that the inverse function is "result - 1" and provide the primitive operations for that.
    - porton 5y ago
      The number of bits is s(X) not X. So, the rest in your response is in error. Why do you think my proofs needs to pre-calculate all possible input-output mappings? I use only verification that a particular input corresponds to a particular output (and I prove that this verification is polynomial-time.) "That isn't what P =? NP is looking for. The forward function, A, isn't a big look-up table. Instead, it's a much smaller set of transformational steps." - no idea what you mean. No comment on obvious (and true) things you said after this.
porton 5y ago
More detailed proof of P=NP with errors corrected: https://math.portonvictor.org/wp-content/uploads/2021/06/pnp-merkle-4.pdf https://math.portonvictor.org/wp-content/uploads/2021/06/pnp...

3 points by porton 5y ago

I prove that an NP-complete cryptocurrency is polynomial time. Comment if you did or did not found an error. No efficient algorithm found.

metalliqaz 5y ago

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

porton 5y ago
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.

nabla9 5y ago

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

porton 5y ago
Because for my proof to work I need polynomial-time hashing.

mgsouth 5y ago

I'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.

porton 5y ago
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".
- porton 5y ago
  Well, https://math.portonvictor.org/wp-content/uploads/2021/06/pnp-merkle-4.pdf https://math.portonvictor.org/wp-content/uploads/2021/06/pnp...
- mgsouth 5y ago
  "n" is the number of bits (what you referred to as "X"). Storing one value into a tree is O(log(X)). However, storing all possible values for X bits is 2^X operations, each of which requires log(X) sub-operations to store it. Pre-calculating all possible input-output mappings requires looking at every possible input value. Thats 2^X. That isn't what P =? NP is looking for. The forward function, A, isn't a big look-up table. Instead, it's a much smaller set of transformational steps. So if A(y) is defined as y+1, you can code it with about X primitive logical operations. One operation could be "output[least significant bit] = xor(input[least significant bit], 1)". That operation causes a transformation to every single input value, and is thus very powerful and economical. Other operations would ripple the carry to the more significant bits; the next-to-least-significant operation transforms half of the input values, the next bit affects one quarter of them, and so on. P =? NP asks if it's always possible to come up with a reasonably small set of transformations that go the opposite way. You can't do that with a process that looks at the discrete values. If it's possible it will require some kind of comprehension of the algorithm's structure. We can't (in polynomial time) create an inverse of "y+1" by listing what happens for each possible input value. We need to recognize that the inverse function is "result - 1" and provide the primitive operations for that.
  - porton 5y ago
    The number of bits is s(X) not X. So, the rest in your response is in error. Why do you think my proofs needs to pre-calculate all possible input-output mappings? I use only verification that a particular input corresponds to a particular output (and I prove that this verification is polynomial-time.) "That isn't what P =? NP is looking for. The forward function, A, isn't a big look-up table. Instead, it's a much smaller set of transformational steps." - no idea what you mean. No comment on obvious (and true) things you said after this.

porton 5y ago

More detailed proof of P=NP with errors corrected: https://math.portonvictor.org/wp-content/uploads/2021/06/pnp-merkle-4.pdf https://math.portonvictor.org/wp-content/uploads/2021/06/pnp...