A thought experiment ...

Suppose a talented amateur stumbles across an algorithm that seems to solve an NP-Complete problem. Let's be specific - suppose we have an algorithm which, given a graph, seems to three-vertex colour it, and the time taken is polynomial in the size of the graph.

Let's further suppose that this talented amateur doesn't have the tools to prove that the algorithm is sub-exponential. They've run lots of graphs through their algorithm, larger and larger instances, and drawn a plot of the performance. It really does appear to be sub-exponential.

Now what?

The obvious thing for academic-type people to suggest is to publish the algorithm, but that has a few problems. Firstly, people don't want to let go of something they see as their own, so publishing is difficult. Secondly, and more importantly, our talented amateur doesn't know how to write it up to make it clear and convincing. But thirdly, and perhaps most importantly, how can our talented amateur get anyone interested?

But perhaps the real problem is the lack of evidence.

To see how this is so, consider factoring integers. That's not an NPC problem, but it illustrates the point with an example most people can imagine easily. So the "size" of a number is how many bits it takes to represent it. Small numbers are easy to factor, but as numbers get bigger and bigger they get harder and harder to factor. So far, so good. But if I give you a number literally at random, there's a one-in-two chance that it has a factor of 2. There's a one-in-three chance that it has a factor of 3. In fact, there's a very good chance that it has a factor less than log(n), where n is the number you're trying to factor. So almost every number I give you, if chosen at random, is really easy to factor. The proportion of numbers that are hard to factor (in some technical sense) gets smaller and smaller. And this seems to be the case with many NPC problems. Consider a graph on N vertices, with edges chosen independently to be in or out with probability p. Depending on p, this graph is either almost certainly three-vertex-colourable, or almost certainly not three-vertex-colourable. More, to decide which is the case is almost certainly trivial. The proportion of graphs that are difficult to three-vertex-colour shrinks as N gets bigger.

How can I say that? The problem is that as instances get bigger and bigger, the proportion of instances that are actually difficult gets smaller and smaller. In general, picking an instance at random tells you nothing, because it's almost certainly easy. So the evidence we have in the plot is unconvincing. We don't know that any of the instances we solved were actually difficult. We may have seen sub-exponential performance because the instances were all "easy."

So, as we say above, now what?

One approach might be this. We know (or at least, we assume) that people in the real world have instances of NPC problems that they need solving. We assume that fast solutions will be worth real money to them. Perhaps we could approach someone and offer our services to solve their NPC problem instances, and thereby earn money. If we then let people know that we're doing this, and possibly advertise, then perhaps people will start to pay attention.

But who to approach in the first place? Who actually has NPC problem instances that are worth real money? And more importantly, how could we persuade them to listen to us, give us their data, and let us solve their problem?

A variant would be to take an existing challenge, such as RSA-220, and solve that. A degree of attention would be garnered, especially if it was swiftly followed by RSA-230 and RSA-232. Perhaps solving the "Eternity II" puzzle would get some attention, especially if it were announced more-or-less at the same time as factorising a challenge number.

Are these the best ideas?

What would you do?

Quotation from Tim Berners-Lee