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.
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.