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


Bryan Olson wrote:
> 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.
>


The whole point of the propositions establishing the equivalence
between Problem IP and Problem IP-bar in my paper is that *extreme
points* of the polytope defined by the constraints correspond to
c.a.s.s. paths (which, in turn correspond to TSP tours). So, I think
what should matter in this context in making an argument such as the
one you are making above, is the number of extreme points of the
polytope compared to the number of paths. The constraints of the model
define a region (not paths directly). The number of paths allowed in
that region is infinite because of (mathematical) continuity.

If Proposition 3 is correct --which I am quite confident it is,
although the proof may need to be communicated better-- then, as
indicated in Proposition 5 of the paper, the number of extreme points
of the polytope will always be at least as great as the number of
c.a.s.s. paths, regardless of the number of cities. (And, this is
nicely demonstrated in the empirical tests).

.

Relevant Pages

  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... variables and constraints that MUST be explicitly considered. ... In fact polytope presented by Diaby ... out that model can give incorrect answer - ... Your BLP model is such set of linear equations, ...
    (comp.theory)
  • Re: My LP Formulation of the TSP: Conclusions
    ... constraints from that model) and for my final model I just made ... While trying to prove it I have discovered factors showing that it is ... polytope" and let us discuss factors of YOUR polytope and WHY it is ... Yanakakkis to be incorrect) and remove it's symmetry (if there are two ...
    (comp.theory)
  • Re: Need help with reordering items
    ... CREATE TABLE Cities ... INSERT INTO Cities VALUES ('New York', ... Please post DDL, so that people do not have to guess what the keys, ... constraints, Declarative Referential Integrity, datatypes, etc. in your ...
    (microsoft.public.sqlserver.programming)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... > I believe I understand what Dr. Moews is trying to do perfectly. ... then the new polytope is not the same as the original one. ... >>>charaterize the original polytope in terms of these constraints as ... >>>want to identify and discard redundent variables and constraints ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... >Either the constraints developed by Moews using his xvariables ... then the new polytope is not the same as the original one. ... then they are redundent with respect to the original polytope. ...
    (comp.theory)