The P=?NP Poll (2002) [pdf]

Richard Karp: (Berkeley, unsure, P!=NP) My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms.

I believe that the traditional proof techniques will not suffice. Something entirely novel will be required.

My hunch is that the problem will be solved by a young researcher who is not encumbered by too much conventional wisdom about how to attack the problem.

Re: The P=?NP Poll (2002) [pdf]

#5

Post by pdpi » Mon, Nov 07, 2016, 4:05 PM UTC

Knuth's perspective on this topic is quite interesting, bordering on the infuriatingly frustrating: he seems to be of the opinion that p=np, but any proof we find for that will be non-constructive and the actual algorithm will evade us.

http://www.informit.com/articles/article.aspx?p=2213858

Re: The P=?NP Poll (2002) [pdf]

#6

Post by lotsoflumens » Mon, Nov 07, 2016, 4:05 PM UTC

justifier wrote: post #4

Richard Karp: (Berkeley, unsure, P!=NP) My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. I believe that the traditional proof techniques will not suffice. Something entirely novel will be required. My hunch is that the problem will be solved by a young res…

>> My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms.

Actually, there has been tremendous incremental progress in inventing better and better algorithms for NP Complete problems. As a result, these problems are more deeply understood now. I think that the gap to poly time is closing fast.

Contrast that with the almost complete absence of progress in proving P != NP.

Also, from a practical viewpoint, many NP Complete problems of industrial size are now solved routinely.

Re: The P=?NP Poll (2002) [pdf]

#7

Post by daodedickinson » Mon, Nov 07, 2016, 4:09 PM UTC

justifier wrote: post #4

Richard Karp: (Berkeley, unsure, P!=NP) My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. I believe that the traditional proof techniques will not suffice. Something entirely novel will be required. My hunch is that the problem will be solved by a young res…

Well, even if it was, it may not be communicable to those speaking a different language.

Re: The P=?NP Poll (2002) [pdf]

#8

Post by nabla9 » Mon, Nov 07, 2016, 4:18 PM UTC

I like Scott Aaronsons approach: Using NP hardness asumption as a physical constraint and seeing what follows.

https://arxiv.org/abs/quant-ph/0502072

Re: The P=?NP Poll (2002) [pdf]

#9

Post by DavidSJ » Mon, Nov 07, 2016, 4:20 PM UTC

pdpi wrote: post #5

Knuth's perspective on this topic is quite interesting, bordering on the infuriatingly frustrating: he seems to be of the opinion that p=np, but any proof we find for that will be non-constructive and the actual algorithm will evade us. http://www.informit.com/articles/article.aspx?p=2213858

It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...

Re: The P=?NP Poll (2002) [pdf]

#10

Post by Jweb_Guru » Mon, Nov 07, 2016, 4:20 PM UTC

lotsoflumens wrote: post #6

justifier wrote: post #4

Richard Karp: (Berkeley, unsure, P!=NP) My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. I believe that the traditional proof techniques will not suffice. Something entirely novel will be required. My hunch is that the problem will be solved by a young res…

>> My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. Actually, there has been tremendous incremental progress in inventing better and better algorithms for NP Complete problems. As a result, these problems are more deeply understood now. I think that the ga…

Sure, in some cases (the easy ones) we can solve NP-complete problems. However, tons of useful instances of NP-complete problems are not particularly close to being solved. We can even characterize fairly well when the instances become hard (for instance, for graph problems the treewidth seems relevant). I see absolutely no evidence that we're anywhere close to constructing a polynomial-time algorithm for any NP-complete problem. If anything, we are slowly finally making some progress on proving P != NP because we are finally getting some nontrivial superlinear bounds on these problems (thus far, the biggest obstacle to proving P != NP has been the difficulty of proving anything about lower bounds on runtime that isn't directly tied to space consumption).

Seriously, if you're interested in this approach ("well, in practice we can solve the problem if [insert thing here] is bounded"), check out the field of parameterized complexity. It's very popular in the database area. It also reveals some very sharp limits to tractability for these problems in practice, not just in theory.