3 ms·
Are you looking for context regarding how this proof ended up in a prestigious academic journal (when the journal had already planned to reject it) or a more ge
by shadowgovt 5y ago
Are you looking for context regarding how this proof ended up in a prestigious academic journal (when the journal had already planned to reject it) or a more general overview of why any proof that P=NP will likely show up first not in an academic journal, but in a catastrophically massive security breach that lays bare all of the secret information from multiple organizations simultaneously?
- allochthon 5y ago> a more general overview of why any proof that P=NP will likely show up first not in an academic journal, but in a catastrophically massive security breach that lays bare all of the secret information from multiple organizations simultaneously? This is probably what I was looking for. Is there a good discussion of this topic?
- herodotus 5y agohttps://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem
- LatteLazy 5y agoI 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 agoI thought it was, that the proof of equality would have to be a general algorithm to transform one into the other.
- csnweb 5y agoThere 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 agoIn 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 agoIn 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 agoThis 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 agoI 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 agoProving 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 agoMore 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.