Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"



Saenta@xxxxxxxxx wrote:
> I agree with Bryan, there must be a flaw (somewhere!).
>
> Indeed, statement :
>
> "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.

>
> Diaby's paper - as (too!) many others, like Ivanov, Grover, Moscu,
> Anand, etc...- are not relevant to P v. NP problem : starting from
> elementary &naivistic considerations, they invariably make lethal
> mistakes on the road to 'excessively optimistic' claims...
>

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 right level to deal with P vs. NP (as noted since the 70's by
> Hartmanis, DeMillo, etc...) is not Computer Science itself (people
> like Sipser & Razborov have crually experimented that in the 80's with
> Circuits & Relativizations methods), but preferably : Logic & Set
> Theory!
>
> Bests.
>
>
> Bryan Olson <fakeaddress@xxxxxxxxxxx> wrote in message news:<bkpue.1329$N22.509@xxxxxxxxxxxxxxxxxxxxxxxxxx>...
> > moustapha.diaby@xxxxxxxxxxxxxxxxxx wrote:
> > moustapha.diaby also wrote ...
> > >>> > Set x(i,s,j) = y(i,s,j,i,s,j) at the start of each iteration.
> >
> > [Bryan Olson wrote:]
> > >>>Then those y values of the form y(i,s,j,i,s,j) will be at least
> > >>>as large as lambda.
> > >>
> > >>When lambda is their minimum?
> > >
> > > You are actually correct on this point. So ignore my comment above.
> > >>
> > >>>How do you handle the others? You can't
> > >>>subtract lambda, because that could be negative. You can't leave
> > >>>them as they are, because then constraints the proof relies upon
> > >>>won't hold.
> > >>
> > >>What specific constraints are you referring to?
> > >
> > > The question above remains: What specific constraints are you referring
> > > to?
> >
> > The argument for Proposition 3 cites 2.21, 2.22, 2.28, and 2.29
> > as if they held for y' (the final "adjusted y"). The latter two
> > are not directly constraints, but are proven assuming other
> > constraints on y.
> >
> > > What would cause them to stop holding (since the solution at hand
> > > is feasible)?
> >
> > If you subtract lambda from all the y[u,p,v,k,r,t] values, some
> > can become negative. If you just subtract lambda from values of
> > the form y[i,s,j,i,s,j], then constraints such as 2.21 don't
> > hold.

.