Re: P=NP: Linear Programming Formulation of the TSP


Yajun wrote:
> Well, I searched a little bit. The paper that I mentioned should be
> this one in STOC'88:
>
> http://portal.acm.org/citation.cfm?id=62232
>
> It mentioned E. R. Swart 's result on P=NP. But I can not find E. R.
> Swart's TR now.
>
> yalding.

Yannakakis proved that Swart's formulation has some kind of "symmetry"
property and uses it to prove that Swart's formulation has eponential
size. My formulation is not symmetric in the sense of Yannakakis, as
discussed in my paper.

.

Relevant Pages

  • Re: P=NP: Linear Programming Formulation of the TSP
    ... Linear Programming Formulation of the Traveling Salesman Problem''. ... it appears that it must imply that the projection of the feasible polytope ... Symmetry under ... because city 1 is treated differently from the other cities. ...
    (comp.theory)
  • Re: monty hall
    ... How rude. ... this one lacking the symmetry of the ... earlier poster's formulation. ... To repeat: ...
    (sci.math)
  • Re: The Epimenides Paradox
    ... and philosopical nattering about the Liar does not use this ... formulation. ... Prev by Date: ...
    (sci.logic)
  • Feynmans Formulation Dirac inspiration
    ... Feynman's formulation, why Dirac corresponds exp[i Int_t1,t2 (dt ... Ali ... Prev by Date: ...
    (sci.physics.research)
  • Re: Shoenfield
    ... Shoenfield's formulation is perfectly standard. ... The formulation of the problem, which should not be surprising, ... assumes that you have at hand Shoenfield's axiomatization of first ... Prev by Date: ...
    (sci.logic)