Re: P = NP paper
From: Louis Scheffer (lou_at_cadence.com)
Date: 5 Nov 2004 08:14:17 -0700
"mechmech" <email@example.com> writes:
>"Peter Fairbrother" <firstname.lastname@example.org> 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."