You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

gjm comments on Efficient Open Source - Less Wrong Discussion

11 [deleted] 15 March 2015 09:24PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (39)

Comments (39)

You are viewing a single comment's thread. Show more comments above.

Comment author: gjm 16 March 2015 09:34:20AM 3 points [-]

about finding mathematical proofs

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?

Comment author: IlyaShpitser 16 March 2015 10:41:41AM *  2 points [-]

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.

Comment author: passive_fist 16 March 2015 06:31:09PM -1 points [-]

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.

Comment author: IlyaShpitser 16 March 2015 07:10:02PM *  0 points [-]

??? 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." (???)

Comment author: passive_fist 16 March 2015 06:28:52PM -2 points [-]

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.

Comment author: gjm 17 March 2015 02:39:37AM 1 point [-]

The burden of proof is on you

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.
Powered by Reddit Powered by Reddit