I don’t think any solution to P vs. NP would necessarily reveal any major new insights. To understand why, you have to think about the nature of the problem. P vs. NP is about (a) worst-case (b) asymptotic complexity of (c) decision problems. However, most of the time we are not concerned with worst-case performance, we are not concerned with asymptotic complexity, and we are not concerned with decision problems.
It takes a bit more effort to formalize this than it does to formalize P vs. NP, but the benefit of this added formalism is that you get a set of problems with far more theoretical and practical importance.
If you meant, strictly and technically, only that a solution to P v NP wouldn’t necessarily do much, then indeed I agree. But if you mean it’s quite likely that if P v NP is resolved then it won’t make much difference, I’m not so convinced.
A solution to P v NP could make a big difference in at least three ways.
Directly. If the answer were that P=NP then it would mean that “efficient” solutions exist to many families of problems not currently believed to have them. These include problems about which it’s reasonable to care a lot—e.g., the problem of finding a proof or disproof, if one exists, of a given mathematical proposition. Now, of course (1) it could be that the only solutions to these take time of order N^1000, with a large constant of proportionality and large lower-order terms, and (2) the proof that P=NP might fail to tell us how to find those solutions at all.
Via the way it’s proved. At present, so far as I know no one has any credible idea how to prove or disprove P=NP. Some of the more plausible-looking approaches are in some sense known not to work. So a proof or disproof of P=NP would most likely need some powerful new ideas. Again, of course it’s possible (1) that actually there’s some extraordinarily unenlightening proof that somehow avoids containing any discernible new ideas at all, or (2) that the new ideas needed are perfectly chosen not to give any insight into other questions of computational complexity. But either of those would be quite a surprise. (And the most plausible way for #1 to happen would be that the proof shows P=NP by supplying an incomprehensible 100-page algorithm for 3SAT or something—but, see above, a constructive proof of P=NP would itself be very exciting.)
Via intuition adjustments. If the answer were that P=NP it would overturn what almost everyone in the field currently thinks. Lots of complexity theorists’ intuitions would need radical readjustment. If you take a whole lot of very smart people who have been hamstrung by completely wrong intuitions and you fix those intuitions, it seems reasonably probable that something good will result.
Again: I don’t disagree with the literal sense of your original (and now reiterated) claim: a solution to P v NP wouldn’t necessarily reveal new insights; maybe there are (apparently epistemically) possible worlds in which P v NP gets resolved and nothing else changes all that much. But if I have to make a bet on how much difference the resolution of P v NP makes, at least if it comes any time soon, I’d bet on “large” over “small”.
the problem of finding a proof or disproof, if one exists, of a given mathematical proposition.
Again, P vs. NP is about decision problems. You’re making the classical mistake, repeated often in pop-sci accounts by non-mathematicians, that P vs. NP is about finding mathematical proofs. It isn’t. An example of a decision problem would be “does a proof to this proposition exist?” or “does a proof to this proposition shorter than N characters exist?” not “find a proof to this proposition.” Depending on the type of proof system, the decision question could be either trivial, NP-complete, NP-hard, or undecidable. In most proof systems we care about, it’s not NP-complete. It’s often NP-hard.
If the answer were that P=NP then it would mean that “efficient” solutions exist to many families of problems not currently believed to have them.
It wouldn’t. You should change would to could. If an efficient solution to SAT had a provable lower bound of O(n^100000000), it makes very little practical difference whether P = NP or not.
So a proof or disproof of P=NP would most likely need some powerful new ideas.
Most likely, and the proof would be interesting indeed and worthy of study. But could it prove anything other than P vs. NP? Would it give any information about which of the five worlds we live in? Maybe, maybe not. Despite the cosmetic similarity, the five worlds question is mathematically quite different from P vs. NP, so there’s no reason to think that it would.
If the answer were that P=NP it would overturn what almost everyone in the field currently thinks.
It’s very, very, very unlikely that the answer is P=NP.
All your points merely serve to reinforce my initial point. You’re talking about non-asymptotic complexity of non-decision problems. This is what people really care about. All I’m saying is that there’s no reason to assign high likelihood to a proof of P vs. NP offering any new insights into the problems people really care about. All you’ve said so far is consistent with this claim.
I beg your pardon; I was sloppy. What “efficient” P=NP would trivialize is, indeed, not finding proofs but determining which propositions are provable. In practice I very strongly suspect that this would make finding proofs vastly easier too; having established that a certain proposition has a proof, one could “try out” various candidate intermediate steps and figure out a path by a sort of bisection procedure. And it wouldn’t be a big surprise if inspection of a proof-existence-checking algorithm found a way to extract actual proofs from it, but of course that would depend on the details of how it turned out that P=NP.
No, wait. Surely the following questions are in NP. (1) “Does proposition p have a proof whose length is N characters?” (2) “Does proposition p have a proof whose length is N characters and whose first n characters are c1...cn?” If so, then P=NP implies a polynomial-time procedure where first you nail down a possible length, then you find characters one by one. The time this takes is polynomial in the length of the proof, so of course it’ll be less than helpful if the proof is inhumanly long, but the point is that the problem here isn’t that PvNP is only about decision problems.
It wouldn’t. [...]
I do think it would have been better if you had read the whole of the paragraph you were criticizing and observed (1) that there was a reason for the quotation marks around “efficient” and (2) that I already explicitly made the same point you were making.
could it prove anything other than P vs. NP?
Gosh, what a good point. If only I’d thought to say something about that. Oh, wait, I did; that was actually what pretty much the whole of that paragraph was about.
It’s very, very, very unlikely that the answer is P=NP.
Right. (“It would overturn what almost everyone in the field currently thinks”.)
no reason to assign high likelihood [...] new insights into the problems people really care about
You have given no justification at all for this; you’ve merely made the (correct but I think not very interesting) observation that it’s theoretically possible so far as we currently know that someone might resolve PvNP without such new insights, and passed without comment over everything I wrote that addresses the question of how plausible that really is.
Obviously you’re under no obligation to engage at all with what I write, but if you don’t want to then why bother replying at all?
If so, then P=NP implies a polynomial-time procedure where first you nail down a possible length, then you find
characters one by one.
Yup! Even the decision version of the P vs NP question is certainly about search, for this reason (contrary to what the grand parent is claiming). One can generally solve optimization problems via a decision algorithm by paying at most a polynomial cost, precisely as you suggested.
I seem to remember that Levin’s work was about the optimization version of P vs NP, and Cook’s work was about the decision version. They are both given credit these days.
This is only true if P=NP, which is very unlikely! If P=/=NP, the far more likely scenario, then we get no new information about the time complexity of search.
If the decision versions of sets P and NP are not equal, then this implies the search versions of sets P and NP are not equal also. This is because if they were equal, we could use a polynomial algorithm for a search version of an NP-complete problem to solve the decision version of that NP-complete problem in polynomial time, and thus all problem in the decision version of NP are also in the decision version of P.
If the search versions of sets P and NP are not equal, then we get a lot of information about the time complexity of finding proofs that are easy to check as valid (e.g. most proofs mathematicians care about). In particular, there will be no general way of finding an easy-to-check-as-valid proof (of length N) of a statement in time polynomial in N, if the statement and corresponding proof encode an NP-complete problem and solution of some sort.
That is, “either there is no insight in mathematics in general, or the Church-Turing thesis is false, and humans are capable of crazy things.” (???)
Gosh, what a good point. If only I’d thought to say something about that. Oh, wait, I did; that was actually what pretty much the whole of that paragraph was about.
I know what you wrote. What I’m emphasizing is the mathematical differences between the five worlds question and the P vs. NP question, to counter your point.
Right. (“It would overturn what almost everyone in the field currently thinks”.)
Again, I know what you wrote. But this is a point that is worth repeating. And I’ll repeat it again: It is very, very, very, very unlikely that P=NP.
You have given no justification at all for this
The burden of proof is on you, here. I’m saying that there’s no reason to assign high belief to what you claim. You must provide a reason for assigning high belief.
That would be an appropriate response if I had just said “Nope, P v NP is really important and resolving it would probably have useful and interesting consequences”. Since what I actually did was to give some reasons for thinking that, and what you actually did was to dismiss them out of hand and (in some cases) write as if I simply hadn’t written what I did, I’m not sure what further response I can usefully make.
As for the burden of proof, allow me to remind you that your comment that launched this discussion began this way:
A lot of people consider P vs. NP to be the ‘most important problem’ in CS.
It seems to me that that fact is already enough to put the burden of proof on the one who contends that P v NP doesn’t matter. You might, of course, be right, but it seems that “a lot of people”—including, my impression is, most people with substantial expertise in this stuff—take a different view.
(Of course “burden of proof” is, when it’s a useful idea at all, merely shorthand for something to do with prior probabilities. So I can rephrase the above: given that experts in the field generally appear to think that P v NP is important and interesting, and to expect valuable consequences if it’s resolved, it seems obviously reasonable to me to give substantial probability to that in advance of investigating the question more directly. And it turns out that the question is really difficult to investigate directly, and our posterior probability estimates should be largely determined by our priors.)
I will say at slightly greater length why I think it likely (not certain) that a resolution to P v NP would be interesting and valuable:
It’s a question lots of very smart people have thought about a lot, without getting close to a proof.
Therefore, it seems likely that resolving the question will require new ideas that are difficult even for very intelligent experts to find.
It’s quite a central question in its field: lots of other questions regarded as important seem to be closely related to it (e.g., questions about equality or inclusion of other pairs of complexity classes).
Therefore, it seems likely that new ideas powerful enough to resolve P v NP might bring progress on other fairly central open problems in the field.
The suspicion that resolving P v NP is difficult and requires new ideas comes not only from the fact that lots of clever people have failed to do it, but also from various theorems that show that whole classes of approaches can’t work. (E.g., there are oracles relative to which P=NP and others relative to which P!=NP, so no relativizable proof can resolve PvNP either way.)
This at least suggests (though it doesn’t prove) that a resolution of PvNP will need to engage in some fairly deep manner with the actual nature of P and NP. Which in turn seems like reason to think it would require useful new ideas.
The most obvious way for a resolution of PvNP to fail to have interesting new ideas in it would be for it to proceed by exhibiting a polynomial-time for some problem known to be NP-hard—but for that algorithm to be fearsomely and impenetrably complicated, supplying no insight to human readers.
But that would mean showing that P=NP, which would itself be a huge surprise (and overturn lots of things that experts thought almost certainly true). Repairing all those experts’ intuitions seems like it would be likely to lead to progress elsewhere.
And P=NP would be useful in itself, unless the polynomial-time algorithms for NP-hard problems always turned out to take time like 1000000000 n^1000000000. Which seems not very likely since the exponents and constant factors in actual algorithms people have found are very seldom like that.
Historically, resolutions of famous hard mathematical problems have often turned out to help (more or less directly) to make progress beyond the mere resolution of those problems.
For instance, the ideas that led to the proof of “Fermat’s last theorem” have since then also led to a proof of the independently important Taniyama-Shimura conjecture (FLT having required TS only for “semistable” elliptic curves).
Although I say “independently important” it might be better to say that among mathematicians as opposed to readers of popular mathematics books FLT was interesting only because of its connection to the Taniyama-Shimura conjecture.
Another recent example: The key idea behind Perelman’s resolution of the Poincare conjecture (“Ricci flow”) has been used to prove other (related but) separately interesting questions in differential geometry, such as the “quarter-pinched sphere theorem”.
There’s no obvious reason why something similar wouldn’t happen with a resolution of P v NP.
I don’t think any solution to P vs. NP would necessarily reveal any major new insights. To understand why, you have to think about the nature of the problem. P vs. NP is about (a) worst-case (b) asymptotic complexity of (c) decision problems. However, most of the time we are not concerned with worst-case performance, we are not concerned with asymptotic complexity, and we are not concerned with decision problems.
A related, but far more interesting question, is the “five worlds” problem: http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
It takes a bit more effort to formalize this than it does to formalize P vs. NP, but the benefit of this added formalism is that you get a set of problems with far more theoretical and practical importance.
If you meant, strictly and technically, only that a solution to P v NP wouldn’t necessarily do much, then indeed I agree. But if you mean it’s quite likely that if P v NP is resolved then it won’t make much difference, I’m not so convinced.
A solution to P v NP could make a big difference in at least three ways.
Directly. If the answer were that P=NP then it would mean that “efficient” solutions exist to many families of problems not currently believed to have them. These include problems about which it’s reasonable to care a lot—e.g., the problem of finding a proof or disproof, if one exists, of a given mathematical proposition. Now, of course (1) it could be that the only solutions to these take time of order N^1000, with a large constant of proportionality and large lower-order terms, and (2) the proof that P=NP might fail to tell us how to find those solutions at all.
Via the way it’s proved. At present, so far as I know no one has any credible idea how to prove or disprove P=NP. Some of the more plausible-looking approaches are in some sense known not to work. So a proof or disproof of P=NP would most likely need some powerful new ideas. Again, of course it’s possible (1) that actually there’s some extraordinarily unenlightening proof that somehow avoids containing any discernible new ideas at all, or (2) that the new ideas needed are perfectly chosen not to give any insight into other questions of computational complexity. But either of those would be quite a surprise. (And the most plausible way for #1 to happen would be that the proof shows P=NP by supplying an incomprehensible 100-page algorithm for 3SAT or something—but, see above, a constructive proof of P=NP would itself be very exciting.)
Via intuition adjustments. If the answer were that P=NP it would overturn what almost everyone in the field currently thinks. Lots of complexity theorists’ intuitions would need radical readjustment. If you take a whole lot of very smart people who have been hamstrung by completely wrong intuitions and you fix those intuitions, it seems reasonably probable that something good will result.
Again: I don’t disagree with the literal sense of your original (and now reiterated) claim: a solution to P v NP wouldn’t necessarily reveal new insights; maybe there are (apparently epistemically) possible worlds in which P v NP gets resolved and nothing else changes all that much. But if I have to make a bet on how much difference the resolution of P v NP makes, at least if it comes any time soon, I’d bet on “large” over “small”.
Again, P vs. NP is about decision problems. You’re making the classical mistake, repeated often in pop-sci accounts by non-mathematicians, that P vs. NP is about finding mathematical proofs. It isn’t. An example of a decision problem would be “does a proof to this proposition exist?” or “does a proof to this proposition shorter than N characters exist?” not “find a proof to this proposition.” Depending on the type of proof system, the decision question could be either trivial, NP-complete, NP-hard, or undecidable. In most proof systems we care about, it’s not NP-complete. It’s often NP-hard.
It wouldn’t. You should change would to could. If an efficient solution to SAT had a provable lower bound of O(n^100000000), it makes very little practical difference whether P = NP or not.
Most likely, and the proof would be interesting indeed and worthy of study. But could it prove anything other than P vs. NP? Would it give any information about which of the five worlds we live in? Maybe, maybe not. Despite the cosmetic similarity, the five worlds question is mathematically quite different from P vs. NP, so there’s no reason to think that it would.
It’s very, very, very unlikely that the answer is P=NP.
All your points merely serve to reinforce my initial point. You’re talking about non-asymptotic complexity of non-decision problems. This is what people really care about. All I’m saying is that there’s no reason to assign high likelihood to a proof of P vs. NP offering any new insights into the problems people really care about. All you’ve said so far is consistent with this claim.
I beg your pardon; I was sloppy. What “efficient” P=NP would trivialize is, indeed, not finding proofs but determining which propositions are provable. In practice I very strongly suspect that this would make finding proofs vastly easier too; having established that a certain proposition has a proof, one could “try out” various candidate intermediate steps and figure out a path by a sort of bisection procedure. And it wouldn’t be a big surprise if inspection of a proof-existence-checking algorithm found a way to extract actual proofs from it, but of course that would depend on the details of how it turned out that P=NP.
No, wait. Surely the following questions are in NP. (1) “Does proposition p have a proof whose length is N characters?” (2) “Does proposition p have a proof whose length is N characters and whose first n characters are c1...cn?” If so, then P=NP implies a polynomial-time procedure where first you nail down a possible length, then you find characters one by one. The time this takes is polynomial in the length of the proof, so of course it’ll be less than helpful if the proof is inhumanly long, but the point is that the problem here isn’t that PvNP is only about decision problems.
I do think it would have been better if you had read the whole of the paragraph you were criticizing and observed (1) that there was a reason for the quotation marks around “efficient” and (2) that I already explicitly made the same point you were making.
Gosh, what a good point. If only I’d thought to say something about that. Oh, wait, I did; that was actually what pretty much the whole of that paragraph was about.
Right. (“It would overturn what almost everyone in the field currently thinks”.)
You have given no justification at all for this; you’ve merely made the (correct but I think not very interesting) observation that it’s theoretically possible so far as we currently know that someone might resolve PvNP without such new insights, and passed without comment over everything I wrote that addresses the question of how plausible that really is.
Obviously you’re under no obligation to engage at all with what I write, but if you don’t want to then why bother replying at all?
Yup! Even the decision version of the P vs NP question is certainly about search, for this reason (contrary to what the grand parent is claiming). One can generally solve optimization problems via a decision algorithm by paying at most a polynomial cost, precisely as you suggested.
I seem to remember that Levin’s work was about the optimization version of P vs NP, and Cook’s work was about the decision version. They are both given credit these days.
This is only true if P=NP, which is very unlikely! If P=/=NP, the far more likely scenario, then we get no new information about the time complexity of search.
??? Am I missing something?
If the decision versions of sets P and NP are not equal, then this implies the search versions of sets P and NP are not equal also. This is because if they were equal, we could use a polynomial algorithm for a search version of an NP-complete problem to solve the decision version of that NP-complete problem in polynomial time, and thus all problem in the decision version of NP are also in the decision version of P.
If the search versions of sets P and NP are not equal, then we get a lot of information about the time complexity of finding proofs that are easy to check as valid (e.g. most proofs mathematicians care about). In particular, there will be no general way of finding an easy-to-check-as-valid proof (of length N) of a statement in time polynomial in N, if the statement and corresponding proof encode an NP-complete problem and solution of some sort.
That is, “either there is no insight in mathematics in general, or the Church-Turing thesis is false, and humans are capable of crazy things.” (???)
I know what you wrote. What I’m emphasizing is the mathematical differences between the five worlds question and the P vs. NP question, to counter your point.
Again, I know what you wrote. But this is a point that is worth repeating. And I’ll repeat it again: It is very, very, very, very unlikely that P=NP.
The burden of proof is on you, here. I’m saying that there’s no reason to assign high belief to what you claim. You must provide a reason for assigning high belief.
That would be an appropriate response if I had just said “Nope, P v NP is really important and resolving it would probably have useful and interesting consequences”. Since what I actually did was to give some reasons for thinking that, and what you actually did was to dismiss them out of hand and (in some cases) write as if I simply hadn’t written what I did, I’m not sure what further response I can usefully make.
As for the burden of proof, allow me to remind you that your comment that launched this discussion began this way:
It seems to me that that fact is already enough to put the burden of proof on the one who contends that P v NP doesn’t matter. You might, of course, be right, but it seems that “a lot of people”—including, my impression is, most people with substantial expertise in this stuff—take a different view.
(Of course “burden of proof” is, when it’s a useful idea at all, merely shorthand for something to do with prior probabilities. So I can rephrase the above: given that experts in the field generally appear to think that P v NP is important and interesting, and to expect valuable consequences if it’s resolved, it seems obviously reasonable to me to give substantial probability to that in advance of investigating the question more directly. And it turns out that the question is really difficult to investigate directly, and our posterior probability estimates should be largely determined by our priors.)
I will say at slightly greater length why I think it likely (not certain) that a resolution to P v NP would be interesting and valuable:
It’s a question lots of very smart people have thought about a lot, without getting close to a proof.
Therefore, it seems likely that resolving the question will require new ideas that are difficult even for very intelligent experts to find.
It’s quite a central question in its field: lots of other questions regarded as important seem to be closely related to it (e.g., questions about equality or inclusion of other pairs of complexity classes).
Therefore, it seems likely that new ideas powerful enough to resolve P v NP might bring progress on other fairly central open problems in the field.
The suspicion that resolving P v NP is difficult and requires new ideas comes not only from the fact that lots of clever people have failed to do it, but also from various theorems that show that whole classes of approaches can’t work. (E.g., there are oracles relative to which P=NP and others relative to which P!=NP, so no relativizable proof can resolve PvNP either way.)
This at least suggests (though it doesn’t prove) that a resolution of PvNP will need to engage in some fairly deep manner with the actual nature of P and NP. Which in turn seems like reason to think it would require useful new ideas.
The most obvious way for a resolution of PvNP to fail to have interesting new ideas in it would be for it to proceed by exhibiting a polynomial-time for some problem known to be NP-hard—but for that algorithm to be fearsomely and impenetrably complicated, supplying no insight to human readers.
But that would mean showing that P=NP, which would itself be a huge surprise (and overturn lots of things that experts thought almost certainly true). Repairing all those experts’ intuitions seems like it would be likely to lead to progress elsewhere.
And P=NP would be useful in itself, unless the polynomial-time algorithms for NP-hard problems always turned out to take time like 1000000000 n^1000000000. Which seems not very likely since the exponents and constant factors in actual algorithms people have found are very seldom like that.
Historically, resolutions of famous hard mathematical problems have often turned out to help (more or less directly) to make progress beyond the mere resolution of those problems.
For instance, the ideas that led to the proof of “Fermat’s last theorem” have since then also led to a proof of the independently important Taniyama-Shimura conjecture (FLT having required TS only for “semistable” elliptic curves).
Although I say “independently important” it might be better to say that among mathematicians as opposed to readers of popular mathematics books FLT was interesting only because of its connection to the Taniyama-Shimura conjecture.
Another recent example: The key idea behind Perelman’s resolution of the Poincare conjecture (“Ricci flow”) has been used to prove other (related but) separately interesting questions in differential geometry, such as the “quarter-pinched sphere theorem”.
There’s no obvious reason why something similar wouldn’t happen with a resolution of P v NP.