Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
moustapha.diaby@xxxxxxxxxxxxxxxxxx wrote:
> Saenta@xxxxxxxxx wrote:
>>"Proposition 6
>>Computational complexity classes P and NP are equal."
>>
>>-as claimed by Diaby- is nothing but :
>>
>>"PA proves P=NP".
>>
>>I guess many (gifted!) logicians would be 'very happy' to prove such a
>>statement...
>
> No, the argument is that the TSP can be formulated as linear
> programming problem.
While I don't believe the argument is correct, it's structure is
reasonable: here's a polynomial-time reduction from an NP-
complete problem to a polynomial-time problem. If anyone does
find a proof that P=NP that's probably what it will look like.
Pretty much everything outside that argument is extraneous. The
audience for such a paper does not need to be told that the
result would be significant. The importance of TSP is that it is
NP-complete, nothing more. Computing the algorithm for seven or
eight cities is gratuitous.
The "symmetric" discussion does not belong in the body of the
paper; Proposition 2 is never used. If the paper is correct,
then it doesn't contradict other correct results.
> The developments in my paper are supported by emprimental
> (computational) testing. If you do not understand the theory, I think
> that you should at least take into account the fact that the empirical
> testing confirms, exactly, what is predicted in the theory!
The implementation is unconvincing. It only goes up to eight
cities, and city one is fixed. At that point the number of
constraints still dominates the number of possible paths.
--
--Bryan
.
