gotchaMinor
Why does this not prove $P\neq NP$?
Viewed 0 times
thiswhyneqprovedoesnot
Problem
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$?
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$?
Solution
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.
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.
Context
StackExchange Computer Science Q#80168, answer score: 8
Revisions (0)
No revisions yet.