Suppose We Have An Algorithm For An NPC Problem 


I'm actively soliciting reactions to this before I make it generally available and weave it into my bloggy thing. I'd like to know what's clear, what's not clear, what needs explaining, and answers to the question(s) posed. Let me know  email is best. 
Suppose a talented amateur stumbles across an algorithm that seems to solve an NPComplete problem. Let's be specific  suppose we have an algorithm which, given a graph, seems to threevertex 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 subexponential. 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 subexponential.
Now what?
The obvious thing for academictype 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 oneintwo chance that it has a factor of 2. There's a oneinthree 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 threevertexcolourable, or almost certainly not threevertexcolourable. More, to decide which is the case is almost certainly trivial. The proportion of graphs that are difficult to threevertexcolour shrinks as N gets bigger. 
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 RSA220, and solve that. A degree of attention would be garnered, especially if it was swiftly followed by RSA230 and RSA232. Perhaps solving the "Eternity II" puzzle would get some attention, especially if it were announced moreorless at the same time as factorising a challenge number.
Are these the best ideas?
What would you do?
Contents 
Links on this page 

Quotation from Tim BernersLee 