= 27d567bc2d48d9f40e9ccc20ea370b15)
ciphergoth comments on When does an insight count as evidence? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (37)
Wouldn't that imply P != NP since otherwise there would be a counterexample?
There is a known concrete algorithm for every NP-complete problem that solves that problem in polynomial time if P=NP:
Generate all algorithms and run algorithm n in 1/2^n fraction of the time, check the result of algorithm n if it stops and output the result if correct.
Nice! More explicitly: if the polynomial-time algorithm is at (constant) index K in our enumeration of all algorithms, we'd need about R*2^K steps of the meta-algorithm to run R steps of the algorithm K. Thus, if the algorithm K is bound by polynomial P(n) in problem size n, it'd take P(n)*2^K steps of the meta-algorithm (polynomial in n, K is a constant) to solve the problem of size n.
No. It could be that there is an algorithm that solves some NP-complete problem in polynomial time, yet there is no proof that it does so. We could even find ourselves in the position of having discovered an algorithm that runs remarkably fast on all instances it's applied to, practically enough to trash public-key cryptography, yet although it is in P we cannot prove it is, or even that it works.