Difficult Problems

It's fun to think about very difficult problems in mathematics. There is no danger of solving such a problem, so the stress that is associated with easy problems ("if I don't solve this as fast as the guy down the hall, I must be an idiot") is absent. Difficult problems also lead to a large amount of dry wit. This may be due to their difficulty, or due to the people that tend to think about them. I am not sure.

Today I happened upon a thread on open problems in mathematics that are easy to explain on the xkcd maths forum. I didn't feel like doing work, so that was an ace discovery. Two fun problems were mentioned: P?=NP and Ramsey numbers.

P?=NP

P?=NP asks whether a certain class of problems that are "very difficult" are, in reality, merely "rather difficult". Or, closer to the truth, whether problems for which a proposed solution can be checked "rather quickly" can also be solved "rather quickly". "Rather quickly" can still mean several billion times the lifetime of the universe, but it is well defined and quite a bit faster than "rather slowly".

A poster in that thread wrote this rather charming bit:

Re: Open Problems That Are Easy to Explain
Post by EstLladon on Tue Apr 01, 2008 9:15 am UTC

It is slightly off-topic and probably not useful, but lately I like to think about P=NP problem like this: suppose there is an art critic, who can by looking at a picture immediately say whether it is good or bad. Can he draw a good picture? Sure he can - he can just draw a picture, if he does not like it he throws it away. Doing that a lot of times he will at some point draw a good picture (this is mathematical world, so there is only a finite number of possible pictures of given size). But this takes a lot of time. Can he do it faster? (like drawing a small but good piece, and then trying to draw another one trying not to ruin it :) )

That was cute enough to remind me of a paper I read recently. In 2002, William Gasarch decided it would be a good idea to take a poll among mathematicians and computer scientists to check the prevailing opinion: does P=NP or does it not? Can the art critic do it faster, or not? The author's introduction is a kind of "eh, this problem is too hard to actually think about right now":

The P=?NP problem has been open since the early 1970’s. Many people-hours have been spent thinking about it and many (perhaps irrelevant) things are known. Are we making progress? This is hard to say for sure. When will it be solved? Also hard to say. Lacking the mathematical tools to answer these questions rigorously we turn to rather non-rigorous means—polling. Almost all respondents are people whose opinions can be taken seriously.

It contains some wonderful bits like this one, courtesy of Ron Fagin (IBM Almaden Research Center):

I’ve proven (at least twice) that NP does not equal co-NP (and hence P does not equal NP). I’ve also proven (also at least twice) that NP equals co-NP. My most recent proof that NP does not equal co-NP occurred about a week ago as I write this, and the proof survived for about half an hour (not quite long enough for me to run it by someone else). My longest-surviving proof that NP does not equal co-NP (about 5 years ago) survived for about 3 days and fooled some very smart people into believing it.

and my favourite, from Stuart Kurtz (U of Chicago):

Knowing Ketan Mulmuley, I live in fear that the solution will be via algebraic geometry, and it will come soon enough that I’ll be expected to understand it. An alternative nightmare is that the undergraduate who solves it will publish his solution in French.

Ramsey Numbers

Mathworld explains Ramsey numbers better than I can, and instead of pilfering their article, I'll just direct you there.

Now that you know what they are (or not, but don't worry, all you need to know is that R(x,y) is some integer that is infernally more difficult to find as x and y grow even a tiny bit), you can appreciate this Paul Erdos quotation, courtesy of that same xkcd thread & Wikipedia:

Imagine an alien force, vastly more powerful than us landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they asked for R(6, 6), we should attempt to destroy the aliens.

So that's the kind of stuff I read. Anyway: I'm three books behind or so. One of these days I'll post about them.