A decade ago, Bill Gasarch conducted an informal poll asking computer scientists and mathematicians various questions related to whether or not P was equal to NP. He asked when people thought the problem would be resolved, which was it would be resolved, and what techniques they thought would be used. One thing that is striking about Gasarch's data is that a surprisingly large fraction of serious computer scientists seem to think that P = NP. Moreover, while Gasarch notes that some of those individuals explicitly said they were saying it for the sake of being contrary, a large fraction also were simply unwilling to guess which way it would be resolved.
Now, Gasarch is again conducting such a poll. I am noting this here, because he is accepting emails from not just computer scientists but individuals in general, although he wants people to note their academic background. Also, please note that he wants replies by email. Apparently some people have already failed to note this and have added them as comments to his announcement post.
My own opinion (which I will submit via email shortly), is that P != NP, and I'm about 95% confident in this regard. I assign low probability to the weirder possible results involving undecidability in ZFC. I have no idea when the problem will be resolved, and I have no idea what techniques will be used to resolve it, although the techniques used by both Mulmuley and Ryan Williams look interesting. Obviously, I'm not a computer scientist, so my opinions on these matters should be taken with a large dose of salt.
Gasarch's poll also has an open-ended question allowing one to pontificate on related issues. Unfortunately, I really don't have any strong opinion on any related issues other than something like "derandomization is nice, yay?" The obvious related question of whether P = BPP seems tough. A lot of people are convinced that this is the case, and there's been a lot of success in the last few years with derandomizing algorithms, but my impression is that there's very little in the way of general techniques of how to do this systematically.
I'm also curious what readers of this blog thing, so feel free to leave your speculations in the comments.
Subscribe to:
Post Comments (Atom)
4 comments:
I have no idea what "P = NP" is supposed to mean, and I find it very provoking that you give no explanation of it (nor does the linked paper). If your blog is addressed only to readers who know what it means, then it just got a lot less interesting to me.
Thanks. That's an excellent point. I think I'll do a blog entry explaining the problem. You are very likely not the only reader who doesn't know about this problem. I'll say for now just that it is a very deep problem in computer science that has a million dollar prize for its resolution. Expect an explanatory blog entry in about 24 hours.
Joshua: The other point about P=BPP worth mentioning is that it's known to follow from circuit lower bound conjectures that look extremely plausible (arguably, even more plausible than P!=NP): for example, that there's a language in E=DTIME(2^n) that requires exponential-size circuits. (That was shown by Impagliazzo and Wigderson in 1997.)
MKR: You could, y'know, google ... Joshua writes a math blog, and it's not exactly an obscure question.
Scott, yes that's a good point about the circuit bounds although honestly I'm not sure I know nearly enough about that stuff to really evaluate the plausibility of those conjectures other than at a very weak level. (My primary area is number theory not comp sci).I agree that they do look plausible.
As to your comment about MKR, yes this is a math blog, but it is (as the title says) a blog about a fair number of other subjects, and I generally do try to make the math entries at least somewhat accessible to not as mathy people, which in this case I failed to do.
Post a Comment