5 ms·

I don't think a proof that P=NP is the same as actually turning all NP problems into P problems. You could prove it's POSSIBLE to break all current security wit

I don't think a proof that P=NP is the same as actually turning all NP problems into P problems. You could prove it's POSSIBLE to break all current security without actually breaking any of it.

nraynaud 5y ago
I thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.
- csnweb 5y ago
  There might be a possibility to prove that such an algorithm exists without knowing how the algorithm works exactly / being able to construct a runnable version of it.
- erik 5y ago
  In theory a proof could show that such an algorithm must exist without producing the algorithm itself. Though that's not what this linked paper tries to do.
  - lovecg 5y ago
    In fact if there was a non-constructive proof, we would already know a polynomial time algorithm for solving any NP problem: just iterate over all program lengths (from 1 to infinity) and then iterate over all programs of that length n, running each for n steps. If one of the guesses produces the correct answer (which it must if P = NP), we have a polynomial time algorithm! Wild, huh?
    - CaptainNegative 5y ago
      This finds a certificate for positive instances, but without a complexity bound can this be made to solve the decision problem in the presence of negative instances?
      - deleted 5y ago
        [deleted]
      - lovecg 5y ago
        I had to look this up since it’s been a while, but looks like no - this is not a full solution. It correctly accepts the positive instances in polynomial time but no algorithm is known that would fully decide all instances in polynomial time.
DrBenCarson 5y ago
Proving it’s possible is the hard part, though. Granted, if you did actually implement a P-time algorithm that would also do the former.
dragontamer 5y ago
More importantly, if it turns out that P = NP through a O(n^1,000,000,000,000) algorithm, then you've proven P = NP but no one is breaking much security any time soon. But even finding a O(n^big_number) (where big_number is a googleplex, or graham's number... or some other absurdity) would be a huge advancement in theoretical computer science.

I don't think a proof that P=NP is the same as actually turning all NP problems into P problems. You could prove it's POSSIBLE to break all current security without actually breaking any of it.

nraynaud 5y ago

I thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.

csnweb 5y ago
There might be a possibility to prove that such an algorithm exists without knowing how the algorithm works exactly / being able to construct a runnable version of it.
erik 5y ago
In theory a proof could show that such an algorithm must exist without producing the algorithm itself. Though that's not what this linked paper tries to do.
- lovecg 5y ago
  In fact if there was a non-constructive proof, we would already know a polynomial time algorithm for solving any NP problem: just iterate over all program lengths (from 1 to infinity) and then iterate over all programs of that length n, running each for n steps. If one of the guesses produces the correct answer (which it must if P = NP), we have a polynomial time algorithm! Wild, huh?
  - CaptainNegative 5y ago
    This finds a certificate for positive instances, but without a complexity bound can this be made to solve the decision problem in the presence of negative instances?
    - deleted 5y ago
      [deleted]
    - lovecg 5y ago
      I had to look this up since it’s been a while, but looks like no - this is not a full solution. It correctly accepts the positive instances in polynomial time but no algorithm is known that would fully decide all instances in polynomial time.

DrBenCarson 5y ago

Proving it’s possible is the hard part, though. Granted, if you did actually implement a P-time algorithm that would also do the former.

dragontamer 5y ago

More importantly, if it turns out that P = NP through a O(n^1,000,000,000,000) algorithm, then you've proven P = NP but no one is breaking much security any time soon. But even finding a O(n^big_number) (where big_number is a googleplex, or graham's number... or some other absurdity) would be a huge advancement in theoretical computer science.