Doesn't argue that "P=?NP" is an ill posed problem, but rather that solving it may not be very important, as the details matter at lot for the implications the result may have. There are a lot of solutions that would settle the problem, without having any influence on the practical state of affairs.
Introduces the term 'SAT' at some point, without explaining what it means. Wikipedia isn't helpful.
SAT is the boolean satisfiability problem, a simple NP-complete problem often used to prove the other problems are NP-complete. An instance of SAT is a boolean formula, and the answer to it is yes if and only if the formula can be true for some assignment of variables. 3SAT is the same problem, only with the formula in a conjunctive normal form and each clause having exactly three variables.
Also, it seems the poster is really just trying to get attention. Complexity theorists do know all that and have spent a lot of time trying to see which postulated consequences of P?=NP are necessary and which are not.
(If I were to argue it is an ill-posed question, I'd go more in the direction of CO-NP (which is the set of problems for which "NO" answers have short certificates), and why this really strong emphasys on "yes" certificates for NP problems)
And, also, the "easy" equals "polynomial time" is (a) a good heuristic, if you assume computational power increases exponentially (hence, a problem will be solvable in the foreseeable future if all it needs is polynomially more processing power for larger instances); (b) it is an easy to study class, since it is composable; (c) not the only thing complexity theorists argue about (ie, P=NP means practical bounds for some problems and collapses a lot of classes that are not trivially seen to be equal, like AM and MA)
I think your evaluation of the post may have been somewhat rushed.
- The poster is a notable complexity theorist and is not "just trying to get attention".
- Doron Zeilberger's "a lot more interesting" take is completely subsumed in Richard Lipton's blogpost, in that it mentions other possibilities beyond the basic "what if it's polynomial with a really huge exponent" scenario.
- Assuming computational power to increase exponentially indefinitely is completely ridiculous, and without the "indefinitely" part this assumption no longer works to justify "easy = P".
- It is trivial to say that if P=NP, then AM=MA, because both AM and MA are in the polynomial hierarchy, and if P=NP, the hierarchy collapses completely.
- The most important point to be taken away from the blogpost is not just that "easy = P" is an assumption that's been held on too unreflectively and may not turn out to be true. It's that studying what this assumption means, how it could break down, and why it hasn't, by and large, broken down so far, may get us closer to understanding P ?= NP.
You have a point. My closeted complexity theorist persona thinks it would be a lot more interesting to study the special cases of P (not just LOG, but seeing how O(n) and O(n²) or "NO(n)" problems behave) instead of the most general cases.
In general, I think blogs should omit introductions to such basic material. It makes more sense to collect the introductions in one place (usually textbooks, but certainly I would welcome someone blogging about intro to something -- see http://www.scottaaronson.com/democritus/ ).
He could explain SAT, but then shouldn't he also explain what a randomized algorithm is, why P=NP is (as he says, possibly) relevant to circuit design, what P and NP are, etc. The problem with this approach is that it doesn't know where to stop (explaining what an algorithm is?).
It's not the material that is the problem, it's the term. I understood the entire blogposting, except for that term. Now that someone explained it, I understand what it means and why it's important. I'm a physicist by training and a software engineer by profession; I think I qualify as the target audience for such a blogposting?
SAT is an abbreviation not an acronym. It stands for SATisfiability, as in http://en.wikipedia.org/wiki/Boolean_satisfiability_problem . The blog on P=NP doesn't appear to mention it despite having 3 posts tagged as SAT. Sometimes we don't realise we're using jargon or we don't realise the wider audience we might be addressing.
Edit: Oops, must refresh before re-joining a HN thread.
I once heard Manuel Blum say that it could be shown that the result can be neither proven nor disproven given our framework of mathematics, similar to the Continuum Hypothesis. In this case, I would call P=NP an ill-posed problem.
I think the OP makes great points in his article, but the title of the blog post is wrong. He really speaks of how the scope of P=NP is misconceived by most people.
Well, even if a given logical theory cannot decide P=NP, it is still a well-posed problem. Either there is a polynomial-time algorithm for SAT or there isn't - no middle-ground here.
But I agree, the blog isn't about this issue at all.
Either there is a polynomial-time algorithm for SAT or there isn't - no middle-ground here.
Statement of the continuum hypothesis: There is no set whose cardinality is strictly between that of the integers and that of the real numbers.
You can provide your argument against the continuum hypothesis. No middle ground? There might not be a polynomial-time algorithm for SAT... but how would we know? You might not be able to prove that one does not exist. The absence of evidence is not the evidence of absence. And we could be eternally locked in this state.
Middle ground exists, for constructivists, those who don't admit the law of the excluded middle (that any statement must be either true or false). And I think most theoretical computer scientists are of this persuasion.
OK, I see what you mean, but I would argue that P=NP is a question of a very different nature than CH.
CH is a statement about the existence of an abstract infinite set, so it is not that surprising that its truth depends on your very definition of a set, an elusive object with multiple possible meanings.
On the other hand, P=NP is a statement about boolean formulas, Turing machines and polynomials. None of these are elusive, they are very cleanly defined, trivial concepts. So it's a very well-posed question.
Of course, we could still not be able to prove the (non)existence of a polynomial algorithm for SAT in ZF set theory. In that case, too bad for ZF, but whether P=NP is still a meaningful question.
The problem is that if it can be proved that P=NP can't be proved or disproved, that constitutes a proof that P!=NP, since it proves that you won't ever come up with an algorithm, which is what the question is really about in the first place.
This being math, one can imagine ever more finely sliced arguments being made, but a "simple" proof that P=NP is forever unsolvable is itself a proof ("the probability that we will find such an algorith is 1 in 10^100"), for all practical and most theoretical (though not all) purposes.
This comment shows you don't know the definition of the problem. The P?=NP problem is defined in such a way that it is either true or not.
P- the set of languages that can be recognized by Deterministic Turing Machine in O(n^k) for some fixed k, n-length of input.
NP - the set of languages that can be recognized by NON-Deterministic Turing Machine in O(n^k) for some fixed k, n-length of input.
No it doesn't! Justify your claim. I just stated the definition of the P?=NP problem. You can find it in any good book on complexity theory. For example:
I was not refering to your definition of P and NP (which I've just reread and I think it's not good; you want "accept", not "recognize"). I was refering to the fact that you do not make the difference between "true" and "provable", which can be found in any standard introductory book on logic; or, if you prefer a novel, Hofstadter's Goedel, Escher, Bach: an Eternal Golden Braid.
First of all- the definition is not mine. It is what is in the books. The terms "recognize" and "recognizable" is defined in the context of complexity theory. So are the terms "decide" and "decidable". "Accept" is not. So when you say you don't think some definition is good please read the exact definition first. There are many serious and great mathematicians and computer scientist involved in that theory and it is irrespectable to them to comment it without being familiar with it.
Second - What I meant to say in my first comment is that the way P?=NP problem is defined it is provable. The fact that it is provable can be proved easily and I will leave this as exercise to you.
Dude, you have no idea what you're talking about. So please stop with the bullshit about great mathematicians and computer scientists when this has nothing to do with them -- only with you -- you cannot accept being wrong. Do your homework first.
Recognizable is not the same thing as acceptable. For example, some undecidable languages are recognizable by Turing machines.
You can leave it as an exercise for anyone you wish, but your assertion (existance of a simple metaproof that there is [a proof of either P=NP or P!=NP]) is false. I base my assertion about your assertion on the fact that about 40 years of research has not produced such a metaproof.
I wouldn't be so sure that P=NP not provable <=> de facto P!=NP.
It's at least not obviously inconceivable that one might stumble upon an algorithm for SAT or traveling salesman whose running time on all known inputs appears to be polynomial but for which a proof of its asymptotic running time might prove extremely elusive (in much the same way that so far as we know the riemann hypothesis appears to hold but proof remains elusive).
You're really moving the goalposts here: if it's already proven that P==NP is undecidable (your supposition) then of course you couldn't prove that the algorithm, say, solved arbitrary instances of SAT in time polynomial in their size; such a proof would prove P==NP => contradiction of undecidability of P==NP.
I was specifically critiquing this assertion:
- since it (P=?NP shown unprovable) proves that you won't ever come up with an algorithm
...which isn't exactly right (you're drawing too strong a conclusion from your supposition): in a "P==NP is undecidable" universe there's nothing (apparently) stopping there being polynomial-time algorithms for NP-complete problems, just a barrier preventing proof that a given algorithm's asymptotic performance puts it in P.
or - another fun possibility - you could have a provably polynomial-time algorithm that seems to solve SAT, but you can't prove or refute its correctness.
Actually: I think you meant what I'm saying in the earlier version of this comment. But yes: if "P==NP is undecidable" holds then for any provably-polynomial sat-"solver" the following possibilities hold:
- you'd be able to find a proof it was an invalid "solver" (eg: the algorithm that assigns 'YES' to each of the N variables is provably polynomial and provably incorrect)
- you wouldn't be able to find a proof it was incorrect (in a strong sense: this isn't 'because you aren't clever enough' but b/c you've stumbled upon one of the 'true' polynomial-time algorithms, ergo there can't be a valid proof it's an invalid solver)
I'd guess you couldn't prove that a given polynomial-time algorithm couldn't be shown to be "provably known to be incapable of invalidation"; such a proof => doesn't exist a counterexample (in this case a SAT instance it doesn't get the right answer for), b/c such a counterexample is a refutation => proof the algorithm is correct => contradiction of "P==NP undecidable", but I won't remove the 'I'd guess' from that unless I had a better understanding of the field, as this kind of reasoning is the kind of thing where the technicalities are the important things, and I'm not up to speed on them.
Thus in the "P==NP undecidable" universe if you found a creepy algorithm -- in your example provably-polynomial but not known to be correct or incorrect, but "empirically" correct over a very extended period of time -- you'd know not to waste time trying to prove it correct (b/c such a proof would be obviously impossible) but you'd see every attempt at proving it invalid also fail, like you said.
If David Hilbert woke up in 1000 years he wouldn't ask "Does P=NP?" but "what progress have we made on P=NP?". Once the Riemann Hypothesis is done with, it's done with, but P=NP or P!=NP opens up whole new lines of discussion.
That said, P=NP could be independent of ZF[1], and if that was shown we'd be scratching our heads asking what P=NP actually means.
According to the Time Hierarchy theorem ( http://en.wikipedia.org/wiki/Time_hierarchy_theorem ), for each number k > 1, there exists a problem in P that can be decided (solved) in O(n^k), and not decided (solved) in O(n^j) for each j in [1, k).
This was the first time I heard of this theorem (was googling for something I thought would weaken the author's point), and it really strengthens the authors argument - I thought his example of O(n^10) algorithms was sort of a fallacy but it appears not. If I'm properly understanding the Time Hierarchy Theorem, it is a very strong argument for what the author is suggesting (and somewhat disappointing for me, because I wish he were wrong).
27 comments
[ 0.29 ms ] story [ 53.1 ms ] threadIntroduces the term 'SAT' at some point, without explaining what it means. Wikipedia isn't helpful.
Also, it seems the poster is really just trying to get attention. Complexity theorists do know all that and have spent a lot of time trying to see which postulated consequences of P?=NP are necessary and which are not.
(If I were to argue it is an ill-posed question, I'd go more in the direction of CO-NP (which is the set of problems for which "NO" answers have short certificates), and why this really strong emphasys on "yes" certificates for NP problems)
Doron Zeilberger's take on that ( http://www.math.rutgers.edu/~zeilberg/Opinion98.html ) is a lot more interesting.
And, also, the "easy" equals "polynomial time" is (a) a good heuristic, if you assume computational power increases exponentially (hence, a problem will be solvable in the foreseeable future if all it needs is polynomially more processing power for larger instances); (b) it is an easy to study class, since it is composable; (c) not the only thing complexity theorists argue about (ie, P=NP means practical bounds for some problems and collapses a lot of classes that are not trivially seen to be equal, like AM and MA)
- The poster is a notable complexity theorist and is not "just trying to get attention".
- Doron Zeilberger's "a lot more interesting" take is completely subsumed in Richard Lipton's blogpost, in that it mentions other possibilities beyond the basic "what if it's polynomial with a really huge exponent" scenario.
- Assuming computational power to increase exponentially indefinitely is completely ridiculous, and without the "indefinitely" part this assumption no longer works to justify "easy = P".
- It is trivial to say that if P=NP, then AM=MA, because both AM and MA are in the polynomial hierarchy, and if P=NP, the hierarchy collapses completely.
- The most important point to be taken away from the blogpost is not just that "easy = P" is an assumption that's been held on too unreflectively and may not turn out to be true. It's that studying what this assumption means, how it could break down, and why it hasn't, by and large, broken down so far, may get us closer to understanding P ?= NP.
He could explain SAT, but then shouldn't he also explain what a randomized algorithm is, why P=NP is (as he says, possibly) relevant to circuit design, what P and NP are, etc. The problem with this approach is that it doesn't know where to stop (explaining what an algorithm is?).
Edit: Oops, must refresh before re-joining a HN thread.
I think the OP makes great points in his article, but the title of the blog post is wrong. He really speaks of how the scope of P=NP is misconceived by most people.
But I agree, the blog isn't about this issue at all.
Statement of the continuum hypothesis: There is no set whose cardinality is strictly between that of the integers and that of the real numbers.
You can provide your argument against the continuum hypothesis. No middle ground? There might not be a polynomial-time algorithm for SAT... but how would we know? You might not be able to prove that one does not exist. The absence of evidence is not the evidence of absence. And we could be eternally locked in this state.
Middle ground exists, for constructivists, those who don't admit the law of the excluded middle (that any statement must be either true or false). And I think most theoretical computer scientists are of this persuasion.
CH is a statement about the existence of an abstract infinite set, so it is not that surprising that its truth depends on your very definition of a set, an elusive object with multiple possible meanings.
On the other hand, P=NP is a statement about boolean formulas, Turing machines and polynomials. None of these are elusive, they are very cleanly defined, trivial concepts. So it's a very well-posed question.
Of course, we could still not be able to prove the (non)existence of a polynomial algorithm for SAT in ZF set theory. In that case, too bad for ZF, but whether P=NP is still a meaningful question.
This being math, one can imagine ever more finely sliced arguments being made, but a "simple" proof that P=NP is forever unsolvable is itself a proof ("the probability that we will find such an algorith is 1 in 10^100"), for all practical and most theoretical (though not all) purposes.
http://www.amazon.com/Introduction-Theory-Computation-Michae...
Second - What I meant to say in my first comment is that the way P?=NP problem is defined it is provable. The fact that it is provable can be proved easily and I will leave this as exercise to you.
Recognizable is not the same thing as acceptable. For example, some undecidable languages are recognizable by Turing machines.
You can leave it as an exercise for anyone you wish, but your assertion (existance of a simple metaproof that there is [a proof of either P=NP or P!=NP]) is false. I base my assertion about your assertion on the fact that about 40 years of research has not produced such a metaproof.
It's at least not obviously inconceivable that one might stumble upon an algorithm for SAT or traveling salesman whose running time on all known inputs appears to be polynomial but for which a proof of its asymptotic running time might prove extremely elusive (in much the same way that so far as we know the riemann hypothesis appears to hold but proof remains elusive).
I was specifically critiquing this assertion:
- since it (P=?NP shown unprovable) proves that you won't ever come up with an algorithm
...which isn't exactly right (you're drawing too strong a conclusion from your supposition): in a "P==NP is undecidable" universe there's nothing (apparently) stopping there being polynomial-time algorithms for NP-complete problems, just a barrier preventing proof that a given algorithm's asymptotic performance puts it in P.
- you'd be able to find a proof it was an invalid "solver" (eg: the algorithm that assigns 'YES' to each of the N variables is provably polynomial and provably incorrect)
- you wouldn't be able to find a proof it was incorrect (in a strong sense: this isn't 'because you aren't clever enough' but b/c you've stumbled upon one of the 'true' polynomial-time algorithms, ergo there can't be a valid proof it's an invalid solver)
I'd guess you couldn't prove that a given polynomial-time algorithm couldn't be shown to be "provably known to be incapable of invalidation"; such a proof => doesn't exist a counterexample (in this case a SAT instance it doesn't get the right answer for), b/c such a counterexample is a refutation => proof the algorithm is correct => contradiction of "P==NP undecidable", but I won't remove the 'I'd guess' from that unless I had a better understanding of the field, as this kind of reasoning is the kind of thing where the technicalities are the important things, and I'm not up to speed on them.
Thus in the "P==NP undecidable" universe if you found a creepy algorithm -- in your example provably-polynomial but not known to be correct or incorrect, but "empirically" correct over a very extended period of time -- you'd know not to waste time trying to prove it correct (b/c such a proof would be obviously impossible) but you'd see every attempt at proving it invalid also fail, like you said.
Edited for clarity. Edited again for correction.
That said, P=NP could be independent of ZF[1], and if that was shown we'd be scratching our heads asking what P=NP actually means.
[1] http://www.scottaaronson.com/papers/pnp.pdf
This was the first time I heard of this theorem (was googling for something I thought would weaken the author's point), and it really strengthens the authors argument - I thought his example of O(n^10) algorithms was sort of a fallacy but it appears not. If I'm properly understanding the Time Hierarchy Theorem, it is a very strong argument for what the author is suggesting (and somewhat disappointing for me, because I wish he were wrong).