Re: P = NP paper

From: Louis Scheffer (lou_at_cadence.com)
Date: 11/05/04


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


"mechmech" <bbb@ccc.com> writes:

>"Peter Fairbrother" <zenadsl6186@zen.co.uk> wrote in message
>news:BDB06288.72456%zenadsl6186@zen.co.uk...
>> 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