This paper is making some waves in Operations Research circles:
We solve a 20-year old problem posed by M. Yannakakis and prove
that there exists no polynomial-size linear program (LP) whose
associated polytope projects to the traveling salesman polytope,
even if the LP is not required to be symmetric.
This argument is independent of the P-vs-NP argument, as it doesn't consider the encoding length of the coefficients.
