5
$\begingroup$

Fiorini, Massar, Pokutta, Tiwary and De Wolf (Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Journal of the ACM 62(2):article 17, 2015; PDF, ArXiv) show any linear program that solves travelling salesman needs super-polynomially many constraints.

Suppose $P=NP$ by 'some' method then we can solve the optimal tour explicitly and trivially setup a LP that 'solves' the TSP problem. So $P=NP$ implies that TSP has a poly-size LP formulation. The contrapositive is that TSP has no poly-size LP formulation implies $P\neq NP$. This paper shows TSP needs super-polynomially many constraints.

So why doesn't this show that $P\neq NP$?

$\endgroup$
  • $\begingroup$ Presumably the part you describe as "trivial" isn't trivial at all. Did you try to actually do it? $\endgroup$ – David Richerby Aug 18 '17 at 10:00
  • $\begingroup$ @DavidRicherby actually no but I am surprised.. you have the certificate then why can't you set up a linear program? $\endgroup$ – Brout Aug 18 '17 at 10:12
  • $\begingroup$ I don't really know anything about linear programing. But any time you have a proof of something surprising, the first step is to make sure the proof really is a proof. Anything that is claimed to be "trivial" or "obvious" is immediately suspect: if it really is that easy, it shouldn't take more than a couple of minutes to write out an actual proof of it. And if you can't write out a proof, then there's a gap. $\endgroup$ – David Richerby Aug 18 '17 at 10:20
  • $\begingroup$ @DavidRicherby Just set weights of unneeded edges to $0$ and needed edges to $1$ and 'solve' for 'selecting edges such that sum of edge weights equal to number of vertices' and this is trivial right? your linear programming solver will 'discard 'non-edges' which are by definition $0$ weight edges' and solve for TSP and this reduction suffices no? $\endgroup$ – Brout Aug 18 '17 at 10:25
  • $\begingroup$ @Evil there is no flaw and check Yuval's comment below. $\endgroup$ – Brout Aug 20 '17 at 1:39
6
$\begingroup$

What Fiorini et al. show is the following:

The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete graph on $n$ vertices). (That is, it is the convex hull of the indicator vectors of all Hamiltonian cycles.)

Suppose that $X_n$ is a polytope whose projection over the first $\binom{n}{2}$ dimensions is $P_n$, and let $d_n$ be the number of constraints needed to define $X_n$ (i.e., the number of facets of codimension 1). Then $d_n \geq f(n)$ for some function $f(n) = 2^{\Omega(\sqrt{n})}$.

In other words, they show that TSP cannot be solved using LPs in one particular way. There could be some other way of using LPs to solve TSP which isn't ruled out by their result.

For example, perhaps you could use iterative rounding to solve TSP, at each step solving an LP. This is consistent with the result of Fiorini et al.

The method in your argument is likewise not ruled out by Fiorini et al.

$\endgroup$
5
$\begingroup$

What you're proposing isn't "a linear program for TSP", so it doesn't come into the scope of the proof.

You've observed that, if $\mathrm{P=NP}$, then TSP can be reduced to polynomial-sized linear programs. You're using a polynomial-time Turing machine to perform a slightly more complicated version of the following reduction:

  • if the input graph $G$ has a tour of length at most $\ell$, then output the program $x>1$;
  • otherwise, output the program $x>1$ and $x<1$.

A linear program that solves TSP is one whose only inputs are variables $x_{uv}$ giving the weight of every edge in the graph and $\ell$, giving the target distance. These variables must be instantiated with exactly the TSP instance you're trying to solve (not with some graph produced by a reduction) and the LP must output a valid tour if one exists. Fiorini et al. prove that any such LP must have exponentially many variables.

$\endgroup$
  • $\begingroup$ I think Yuval's answer is more correct. Check his answer on why my attempt is a linear program ( although a silly one). $\endgroup$ – Brout Aug 20 '17 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.