Proposals

[Pete Gonzalez]

At 11:10 6/30/00, you wrote:
>Are you familliar with the Travelling Salesman
>problem?  
>
>[...]
>
>It has been proven mathematically that this is an
>N*P complete problem, meaning there is no way
>to solve the problem in less time than it takes
>to calculate all possible routes and pick the
>shortest one. 

Actually, it's theoretically possible that there exists a clever algorithm which can solve these problems in polynomial time, i.e. the amount of time required to check a single solution.  This is the "P=NP?" question, and despite years of searching we have yet to find a conclusive mathematical proof either way.

It is most people's SUSPICION that NP complete problems can only be solved by brute force, but it would be incorrect to assume that this is true.  History is full of surprising discoveries like simplex and quicksort that contradicted peoples' intuitions about optimality.

-Pete