Sunday, March 17, 2019
Third Poll on P vs NP and related Questions is out now! And the winner is Harambe!
I took a poll of the theory community (and others) about P vs NP and related issues in 2002, 2012, and 2019 (sorry its not an arithmetic sequence --- read the third poll article to see why). The 2002 and 2012 polls are on the web (see here and here ), and now the third poll is out and its here or here . All three appear in Lane's Complexity Column in SIGACT News.
I'll give some highlights and thought about the third poll, but for more read the article. Or read all three and see how opinions have changed over time.
0) How many respondents: 100 the first time, and 152 the second time, 124 the third time.
1) P≠NP is at about 80%. When restricted to people who have thought about the problem a lot (my judgement) then it goes to 99%. The strongest P≠NP is by Lance who says
People who think P=NP are like people who believe Elvis is alive.
I disagree. I think Elvis is alive and is trying to prove P=NP.
2) When will it be solved? 66% thought it would be solved before 2100, a bit more than in prior years. But also more thought it would never be solved. Some commented that a computer might solve it. I doubt that, but I do think this poll will be done by a computer in 10 years.
3) Because I used Survey monkey (1) each question got more answers, and (2) most questions got a forced YES or NO so less funny comments or room for creative answers. People could still leave comments, and some did.
4) Related to point (3): The last time I did the poll P=BPP was thought by everyone who answered the question. This year far more people answered it and quite a few thought P≠BPP. This may be because Survey monkey had a psychological affect of making people vote even if they didn't really know (people who have thought a lot about P vs NP all thought P=BPP). Has there been evidence that P≠BPP that I am unaware of? Or since there has not been that much progress on it maybe they are unequal. 10 years ago I would have thought we would have L=RL by now.
5) The last time I did the poll 10 people thought factoring IS in P and the NSA or the KGB knows that. This time around nobody thought that. Why? Those 10 people have vanished mysteriously.
6) Five people thought P vs NP will be resolved by Harambe. That is more than any person got.
7) Is this poll worth doing? I would say yes (gee, I have to having done his poll three times) because it is good to have an objective record of subjective opinion.
8) I'll give some of my answers: P≠NP, Elvis is dead, and both will be proven in the year 2525. For more about the future see this.
Subscribe to:
Post Comments (Atom)
nice. I looked through it. My question to Bill and Lance,
ReplyDeletehow should I interpret this the following opinion voiced in the survey:
"I can't wait for people to realize that P=?NP is only a question about the existence of a poly-nomial time algorithm, not about the knowledge of one. We already know, for example, that there exists a polynomial time algorithm to decide membership in any given minor-closed graph family; but we don’t know how to really decide it, except for a few actual families"
And yes, that Don Knuth voicing it.
This is a fine point of view. There are indeed some cases where we can show a poly time algorithm exists but cannot find one. Abstractly we can use the knowledge that one exists to find one that involves running lots of Turing Machines, but to REALLY have one may be difficult. For example, for any g there is an O(n^3) algorithm to test of a graph has genus g since genus-g is closed under minors and hence has a finite obstruction set. But the proof that it has a finite obs set is nonconstructive (I do not know if this particular case they know more constrivelty).
DeleteSo indeed, we may one day find that P=NP but the algorithm is non-constructive.
It can't be completely non-constructive because of Levin search. But the proof may not give an effective upper bound on the degree of the polynomial needed to solve SAT.
DeleteIn response to William Hoza's answer:
ReplyDeleteEven if we did find an algorithm that solves SAT in polynomial time, I do not know of any guarantee that we can prove the algorithm's correctness in every case (even if it is correct in every case).
His response, of course, suggests that some finitely-expressible tautologies do not have finite proofs. This goes against my feelings that math is never arbitrary or without reason, since a proof is no more than an explanation of why the tautology is true.
If it weren’t for the possibility of being unable to prove the supposed algorithm’s correctness, the following logic would have applied:
Claim:
Defining any finitely-expressible object x, it is impossible to prove that there is no proof of whether or not x exists.
Not quite a proof:
*Suppose a proof Q exists, showing that it is impossible to prove whether or not x exists.
*We can now conclude that x does not exist because if it did, we could give x as a proof that it does, which would contradict Q. However, this still contradicts Q: we have proven that it does not exist.
*On second thought, x must exist, otherwise we get the above contradiction. But that still contradicts Q: we have proven that x does exist.
*Either way, you can never proof that there is no proof of whether or not x exists, knowing there are only two possibilities: it exists or it does not. We have exhausted both.
Except, simply showing x does not prove x exists, interestingly. That is, showing an object with some property does not prove it has that property.
6) Wrong. Baar Baar Dekho, a British kid of Pakistani Muslim background born in 2005 growing up in the London area found a P=NP algorithm in 2031/32 making an enormous fortune for himself as the West collapsed.
ReplyDeleteI'm late to the party because I only just heard about these poll results. I noticed that one respondent mentioned the consistency of NF (New Foundations) as a problem of interest. For those who are not aware, Randall Holmes has claimed a proof that NF is consistent. I've asked a couple of experts and the situation seems to be analogous to the Kepler conjecture, in that the experts believe that the proof is probably correct, but the details are extremely complicated and so they haven't been able to check everything themselves. Holmes has revised the proof a few times to try to make it easier to understand, but the constant revisions have made the task of checking the proof harder. Holmes is fluent with proof assistants and is seriously considering using one to definitively establish correctness, but it's a highly nontrivial task.
ReplyDeletePerhaps if more people encourage Holmes by expressing interest in the result, it will hasten the full verification of his proof.