Re: P = NP paper

From: Louis Scheffer (
Date: 11/05/04

Date: 5 Nov 2004 08:14:17 -0700

"mechmech" <> writes:

>"Peter Fairbrother" <> wrote in message
>> Allan Herriman wrote:
>> I expect he's serious, but I doubt he's right. However, I haven't read the
>> paper. I can't get the paper to open, and the 45MB of programs are in some
>> unusual format I don't want to think about. Not encouraging signs.
>If you have not read the paper and you don't want to think about his unusual
>code format, how did you come to the conclusion that " you doubt he is
>right". Either you prove him wrong or you let other do it and you read about
>it in the thread.

It's possible to doubt he is right from nothing but the title of the paper.
"P = NP: Linear Programming Formulation of the Traveling Salesman Problem".
This exact approach has been tried *many* times, and always failed.
For example, in 1987 a professor did exactly the same, starting with a
Hamiltonian cycle problem.

At that time, 17 years ago, Bob Silverman (who's a professional in this and
related areas) replied:

"I'm getting tired of hearing about P=NP proofs. It reminds me too much of
the many crackpots from previous generations who tried to 'square the circle'
or 'trisect a general angle' with straightedge and compass. All of the P=NP
proofs reported so far have the same flaw: They try to formulate an NP problem
as a linear program but ALL wind up requiring an exponential number of
variables in the size of the problem instance."

   Lou Scheffer