= 27d567bc2d48d9f40e9ccc20ea370b15)
passive_fist comments on Efficient Open Source - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (39)
I can offer one data point. A lot of people consider P vs. NP to be the 'most important problem' in CS. I personally don't think it's a very interesting problem. I don't think any solution to it would necessarily reveal any major new insights. And I think it's far beyond my abilities to work on.
I'd be pretty surprised if someone solved PvNP without major new insights, but in any case Hamming (in the same place the quotation comes from) is quite explicit that by "important" he doesn't mean "important, conditional on a successful breakthrough" but "important, taking into account the likelihood of getting somewhere". (His example: no one in physics is seriously working on time travel, teleportation or antigravity, not because they wouldn't be vastly exciting and useful but because we don't have a credible line of attack on any of them.)
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:
I'll just leave this here: http://math.stackexchange.com/questions/1892/the-practical-implication-of-p-vs-np-problem
I mostly agree with passve_fist:
The major implication I care about concerns the feasibility of A.I., specifically because I believe "analogy finding" and knowledge reuse to rest on tractable sollutions to the subgraph isomorphism problem.
You could build an AI which restricts itself to solving small cases of the problem, finding "petty" analogies, and growing more complex ones ontop. Any (computationally efficient) algorithm which could find isomorphisms for larger problems directly in polynomial time would blow a "bottom up" analogy finder out of orbit.
Though ofcourse if anyone reading could point out a method for finding subgraph isomorphisms on large graphs that is "good enough" by some standard, I'll be happy to learn of it :)