Why does this not prove $P\neq NP$?

Question

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$?

Answer 1

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.

Answer 2

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.