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

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...

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 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.
.

Relevant Pages

  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... What specific constraints are you referring ... > If you subtract lambda from all the yvalues, some ...
    (comp.theory)
  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... >>>>When lambda is their minimum? ... You can't leave>>>them as they are, because then constraints the proof relies upon>>>won't hold. ... What specific constraints are you referring ... If you just subtract lambda from values of the form y, then constraints such as 2.21 don't hold. ...
    (comp.theory)
  • Re: default values
    ... In merge replication AFAIK it isn't possible to not replicate the defaults ... constraints so perhaps you are referring to default objects? ... could redefine them as default constraints, or you could use a script to be ...
    (microsoft.public.sqlserver.replication)