12 ms·
The P=?NP Poll (2002) [pdf]
- yread 10y ago[2002]
- ColinWright 10y agoUpdated. To my mind still relevant.
- justifier 10y agoRichard 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.
- lotsoflumens 10y ago>> 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.
- Jweb_Guru 10y agoSure, 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.
- lotsoflumens 10y ago>> (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) I probably don't understand the proofs of these bounds - it seems to me though, that any lower bound without some relationship to the time or space to input the problem into some kind of computer, implies a belief that an instance might be solvable in-place, in some physical system. I have some doubts about that ....
- Jweb_Guru 10y agoTo be clearer, a trivial lower bound is something like "the input is of size n and for any n-1 length yes-instance you can find n-length extensions that are no-instances, so you have to check all n elements." It doesn't tell us anything interesting about the worst-case problem complexity. What's been surprising is how hard it is to make meaningful lower-bound statements stronger than that (well, not surprising to people who work on this stuff for a living, I guess). But that doesn't make it more likely that P = NP, really, except in the sense that we (obviously) haven't characterized the entire space of problems in P yet. To more specifically address your "in-place" concerns, you can often formulate the problem in terms of circuit complexity--circuits are inherently parallel, so minimum circuit depth is a good proxy for a required number of steps, and it's also generally agreed that if you can design a circuit to do something it's physically realizable (even though that's arguably not always true, especially in cases with very wide fanout). So a (somewhat) promising direction has been to try to find circuit complexity lower bounds for problems, especially nontrivial ones.
- anandkulkarni 10y ago>> complete absence of progress in proving P != NP We've ruled out a number of techniques and also have shown that any solution must fall into a category avoiding a number of conditions (natural proof, algebrization barrier). Note also Ryan Williams' result separating ACC0 and NEXP. All of that is progress as I see it. It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes.
- lotsoflumens 10y ago>> It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes. I agree, but the search for better algorithms is also more principled. At some point, separating complexity classes looks like counting the number of angels on a pinhead. It's probably interesting in an abstract way for some people - but it's not my cup of tea, as they say.
- bo1024 10y agoIt's true that there has been a lot of practical progress and even theoretical progress, though often of the form "we improve 1.8^n running time to 1.65^n". But... > As a result, these problems are more deeply understood now. I think that the gap to poly time is closing fast. I'd disagree. As we develop more and more understanding of these problems, we still are only improving exponentials to other exponentials (in theory - practice may be different) and so we remain in a fundamental sense as far away from polynomial-time solutions as ever, despite improved understanding.
- Ar-Curunir 10y agoNP hardness is defined in terms of worst-case hardness, not average case hardness. As long as there exists even one instance that makes your algorithm take non-polynomial amount of time to terminate, P won't be equal to NP.
- lotsoflumens 10y agoThat's why I'm becoming increasingly skeptical of the usefulness (in the scientific sense) of complexity theory as it's currently laid out. We already know that instances of NP-Hard problems are either easily solvable, in poly-time, or take exponential time, depending on the location of the instance in the problem space. For example in SAT, the distance of the instance to the critical clause/variable threshold. In subset sum, the density of the instance. It's not the problem class that matters.
- daodedickinson 10y agoWell, even if it was, it may not be communicable to those speaking a different language.
- pdpi 10y agoKnuth'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 http://www.informit.com/articles/article.aspx?p=2213858
- DavidSJ 10y agoIt'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-time_algorithms https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...
- pdpi 10y agoWith the caveat that it can never return false, which means it's not a complete solution.
- Klockan 10y agoThis argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.
- JadeNB 10y ago> This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1. That seems to be an argument for the uselessness of the distinction between P-with-large-exponent and not-P, not for the uselessness of having a reduction of NP to P. Also, it's worth noting that, if one is a theoretical computer scientist, then there is more of interest in the study of computing than what can be done in the universe. (I am a mathematician, and am, as I suspect most of my colleagues, serenely unconcerned with the applicability or non- of my work.)
- nabla9 10y agoI like Scott Aaronsons approach: Using NP hardness asumption as a physical constraint and seeing what follows. https://arxiv.org/abs/quant-ph/0502072 https://arxiv.org/abs/quant-ph/0502072
- Analemma_ 10y agoI second this; check it out even if you're not the type to usually read scientific papers. This is a fun one that's not hard to understand.
- jessedhillon 10y agoDirect PDF link for the lazy (e.g. me): https://arxiv.org/pdf/quant-ph/0502072v2.pdf https://arxiv.org/pdf/quant-ph/0502072v2.pdf
- adilparvez 10y agoA really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesting because there are particular oracle machines for which P^X == NP^X. See https://en.m.wikipedia.org/wiki/Oracle_machine https://en.m.wikipedia.org/wiki/Oracle_machine for references to papers. Also see https://en.m.wikipedia.org/wiki/Almost_surely https://en.m.wikipedia.org/wiki/Almost_surely if you don't know what with probability 1 is. Off topic (but related to almost surely), one of my favourite theorems is Pólya's recurrence theorem which says that a simple random walk on Z^d (lattice) is recurrent for d=1,2 and transient otherwise, so if you get lost on a 1 or 2 dimensional grid, just execute a simple random walk and you'll get back to the origin almost surely! IIRC the probability of recurrence is about 34% in 3d.
- JadeNB 10y ago> A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. Wait, this has to be conditional on something. If P = NP, then P^X = NP^X for any oracle X, right? (It's been a while since my theoretical CS class, so maybe it's my naïve assumption that's not true.)
- adilparvez 10y ago> If P = NP, then P^X = NP^X for any oracle X, right? Edit: No, I think. See child comment by JadeNB. Probably wrong { Yes, since we could just not invoke the oracle. But people do this sort of stuff to study it backwards e.g. what do P^X and NP^X (and any class^X) tell us about P and NP (and any other class). } I hope this is clearer, let {A, B, C, ...} be the set of all oracles. For TM + A: P^A is the class of problems that can be done in P time on this machine. NP^A is the class of problems that can be done in NP time on this machine. Similarly for TM + B TM + C ... This theorem says that if we choose one of these oracle machines uniformly at random then P =/= NP in _its_ model of computation a.s. This is an entirely probabilistic statement about machines that are more "powerful" than standard TMs.
- VodkaHaze 10y agoIs there any probabilistic argument around the proof? For instance, a decade before Wiles' proof of Fermat's Last Theorem, Feynman[1] showed it was extremely unlikely to be false. While you're not getting a million from Clay for that, it something non insignificant that we can use to guide our intuition. [1]http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem
- kamilner 10y agoAs mentioned elsewhere in the thread, if provided with a random oracle A, P^A != NP^A with probability 1. It's not clear though what this actually buys you, intuition wise, since it's already sort of intuitively clear that nondeterministic oracle queries are much more powerful (then again, I guess you could say the same about nondeterministic computing...) http://epubs.siam.org/doi/abs/10.1137/0210008 http://epubs.siam.org/doi/abs/10.1137/0210008 Edit: For those who are interested, the oracle separation gives you one of the few properties we can prove about the nature of any proof of P ?= NP, that it must be 'non-relativizing'. We know a few other properties of any possible proof, described here: http://www.scottaaronson.com/papers/alg.pdf http://www.scottaaronson.com/papers/alg.pdf
- lovamova 10y agoMaybe the solution to P=NP problem is P=NP.
- joaorico 10y ago#8 is a fun one (some of these answers are half-joking): "Proof by contradiction. Assume P = NP. Let y be a proof that P = NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P = NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction."
- surrey-fringe 10y agoIs that true -- that the proof (if we produce one) will be verifiable in polynomial time?
- petters 10y agoIt is not really meaningful to talk about a single instance being verifiable in polynomial time.
- surrey-fringe 10y agoWell I was open to evidence that applies generally, but sure.
- elehack 10y agoTechnically, yes, but practically, no. THEOREMS (the language of correct proofs) is in P; given a correct proof (possibly restricted to being in first-order logic), it can be verified in polynomial time. In the first-order logic case, all you have to do is read the proof from beginning to end and verify that each statement follows from either an axiom or an already-established statement. This is done entirely syntactically, requiring no knowledge of the underlying mathematics. However, to do this requires formalizing the entire proof in machine-checkable format, which is a substantial undertaking even for relatively simple proofs and will likely take far longer than polynomial time.
- paulddraper 10y agoAs petters points out, "X time" has no useful meaning here. An interesting and still valid point, however, is that P=NP may be undecidable (in the sense of Gödel's incompleteness theorem). In other words, our current axioms may be insufficient to prove or disprove P=NP. http://www.scottaaronson.com/papers/pnp.pdf http://www.scottaaronson.com/papers/pnp.pdf > P != NP is either true or false. It’s one or the other. But we may not be able to prove which way it goes, and we may not be able to prove that we can’t prove it.
- averell 10y agoNot a lot of mention of AI for CS, even in 2002. What about (2080+, P/=NP, proof techniques completely opaque to humans). And by that I don't mean mechanical exclusion of special cases like for map-coloring. As mentioned already, there's like a handful of people that understand the FLT proof, that situation is unlikely to improve.
- chronolitus 10y agoFor those that do not have time to read the whole thing, #29 is worth quoting: "Stuart Kurtz (University of Chicago, 2050, P!=NP) [on wether and when proof will be found]: Knowing Ketan Mulmuley, I live in fear that the solution will be via algebraic geometry, and it will come soon enough that I’ll be expected to understand it. An alternative nightmare is that the undergraduate who solves it will publish his solution in French." But it is by far not the only funny opinion in this paper.
- deleted 10y ago[deleted]
- Paul-ish 10y agoI wonder what this survey would look like if done today.
- Lerc 10y agoThis bit makes me wonder > My longest-surviving proof that NP does not equal co-NP (about 5 years ago) survived for about 3 days and fooled some very smart people into believing it. Is this a path towards selecting by insidiousness of mistakes? Can we mistakenly prove something by evolving a method by which no-one can figure out what is wrong with it. Is there a limit to how hard it is to identify a mistake in a false proof? If incompleteness keeps you up at night, how about the possibility of a proof that you can have a mistaken proof in which the mistake was provably unidentifiable.
- Jweb_Guru 10y agoGenerally speaking, if there's a step that isn't clearly logically justified in your proof, the proof is considered wrong. So in most "normal" proof systems, this wouldn't really be a valid technique (that is, the moment someone tried to formalize it they'd run into this roadblock, and if it wasn't trivial to surmount the original proof would be thrown out). That said, there are some sequent calculi where you can do a lot of work in each step, so it might be really hard to figure out whether the step was valid; but I believe cut elimination theorems in those calculi basically assert that you can turn any valid "large step" into a (possibly very long, but finite) sequence of "small steps". From a sociological perspective, since most mathematicians don't use formal methods for most of their proofs, there can of course be proofs that may be right, but that nobody can understand well enough to verify. The ongoing famous example here is that of Shinichi Mochizuki: http://www.nature.com/news/the-biggest-mystery-in-mathematics-shinichi-mochizuki-and-the-impenetrable-proof-1.18509?WT.mc_id=TWT_NatureNew http://www.nature.com/news/the-biggest-mystery-in-mathematic.... Anyway, neither of these seem too relevant to P vs. NP.
- Nomentatus 10y agoReference needed: Once upon a time Turing Machines were my thing. But that was decades ago. Now I think I have a result that's interesting, following up on graduate school work I did way back when... but... reading such things as the P=NP prize problem definition I see that at least some terminology in the field has changed, or at least, concepts have been added. (Such as "language", if I remember rightly.) Can someone point me to sources that will allow me to translate Turing oldspeak into Turing newspeak, and vice versa?
- throwawayaccnt3 10y agoIf investigating a specific result, I would recommend Wikipedia, ComplexityZoo and yes, even CSTheory.StackExchange. There are more comprehensive documents, however (re)learning a field may be an overinvestment to test a single idea.
- Nomentatus 10y agoCertainly it's not in Wikipedia, and if Google knows about it; I've probably visited it. A question in CSTheory.StackExchange might work, though.
- throwawayaccnt3 10y agoWikipedia won't have an entry on every specific problem, but it can come in handy if there's a general idea of what to search for. A quick investigation on "language" reveals "Formal Language" and "Model Theory" are relevant topics.