CarlShulman comments on When does an insight count as evidence? - Less Wrong

11 Post author: alexflint 04 January 2010 09:09AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (37)

Comments (37)

You are viewing a single comment's thread. Show more comments above.

Comment author: CarlShulman 05 January 2010 04:40:48AM 3 points [-]

In a 2002 poll of 100 researchers, 61 believed the answer is no, 9 believed the answer is yes, 22 were unsure, and 8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove.

Comment author: ciphergoth 05 January 2010 11:06:57AM 0 points [-]

8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove.

Wouldn't that imply P != NP since otherwise there would be a counterexample?

Comment author: Christian_Szegedy 06 January 2010 09:30:32PM *  3 points [-]

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.

Comment author: Vladimir_Nesov 07 January 2010 12:52:24PM 0 points [-]

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.

Comment author: RichardKennaway 05 January 2010 11:52:17AM 2 points [-]

Wouldn't that imply P != NP since otherwise there would be a counterexample?

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.

Powered by Reddit Powered by Reddit