Hacker News Reader

Comment by LatteLazy | Hacker News Reader

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.

View on HN

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.

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.

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

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.

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.

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?

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?

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.

Reply on news.ycombinator.com