As far as we know, the first polynomial-sized LP models to be proposed for an *NP-Complete* problem (specifically, the traveling salesman problem (TSP); see Lawler et al. (1985)) are those of Swart (1986; 1987). We do not know of any of the details of those models, but the concensus of the research communities was that their validities were refuted by developments in Yannakakis (1991). The essence of those developments is the showing that “*the* TSP polytope” does not have a polynomial-sized *extended formulation* (EF) which is *symmetric* (Yannakakis (1991)). By “*the* TSP polytope” it is meant the polytope described using the standard or traditional city-to-city (*travel leg*) variables (see our 2023 refutation paper below; or Lawler et al. (1985)) .

Over the past decade, some authors have focused on removing the *symmetry* condition of Yannakakis (1991). In particular, the claim in Fiorini et al. (2011; 2012) is that the traveling salesman and stable set polytopes in the spaces in their natural variables do not have polynomial-sized EFs, regardless of the *symmetry* condition of Yannakakis (1991). More recently, others (typified by Fiorini et al. (2015), in particular) have made the (implicit or explicit) absolute/unconditioned claim that there exists no abstraction of an *NP-Complete* COP in which the defining combinatorial configurations (such as “tours” in the case of the TSP for example) can be modeled by a polynomial-sized system of linear constraints. Refutations of these latter claims are given in the three “refutation papers” provided below, on this page.

The aim in the earlier ones of these papers (2017; 2021) was to provide general explanations of why the existing negative *extended formulations* (EF) results for “*the* TSP polytope” are not applicable to our developments. We show that the reasons for that non-applicability are the same as those for the case of Martin (1991)’s formulation of the MSTP as it relates to Edmonds’ formulation of the MSTP. Also, Yannakakis (1991, pp. 444-445) discusses the fact that Edmonds (1970)’s formulation of the Minimum Spanning Tree Problem (MSTP) is of exponential size (due to its having “TSP subtour elimination”-like constraints), while Martin (1991)’s formulation which includes Edmonds’ variables (and hence, can be viewed as an *extended formulation* of Edmonds’ model) is of polynomial size. This fact has been generally considered in the EF literature as an unexplained paradox. A contribution of these earlier (2017; 2021) papers is that they explain this paradox.

The most recent (2023) of the “refutation papers” is much more specific and direct. In it, we show (in theory and with illustrative examples) that provided an EF (polynomial-sized or not) of the Linear Assignment Problem (LAP) polytope (see Burkhard et al. (2009)) is *exact* and that TSP tour costs can be accurately accounted through linear functions of its descriptive variables, that EF (of the LAP polytope) allows for the solution of the TSP optimization problem, irrespective of whether a further EF of it in the space of the *travel leg* descriptive variables of “*the* TSP polytope” projects to “*the* TSP polytope” or not. Since the feasibility of these conditions for the LAP polytope is not ruled out by any existing result, this means that a finding that “*the* TSP polytope” does not have an *exac*t polynomial-sized EF does not imply that it is “impossible” for a linear program (polynomial-sized or not) to solve the TSP optimization problem. Part of the issue in this regard is what should/should not be considered a meaningful EF when attempting to make inferences about model sizes, as explained in our 2017 “refutation paper.”

## Refutation papers

Diaby, M., M.H. Karwan, and L. Sun (2023). On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the “barriers.

Diaby, M., M.H. Karwan, and L. Sun (2021). On modeling hard combinatorial optimization problems as linear programs: Refutations of the “unconditional impossibility” claims. *International Journal of Operational Research *40:2, pp. 261-278.

Diaby, M. and M.H. Karwan (2017). Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimization problems. *International Journal of Mathematics in Operational Research* 10:1, pp. 18-33.

## Cited references

Burkard, R., M. Dell’Amico, and S. Martello (2009). *Assignment Problems*. SIAM (Philadelphia).

Edmonds, J. (1970) “Submodular functions, matroids and certain polyhedra”, in R.K Guy et al. (Eds.): *Combinatorial Structures and Their Applications*, pp.69–87, Gordon and Breach, New York.

Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf (2011). Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Bounds. *Unpublished* (Available at: http://arxiv.org/pdf/1111.0837.pdf).

Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf (2012). Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Bounds. *Proceedings of the 44 ^{th} ACM Symposium on the Theory of Computing (STOC ’12)*, New York, NY, pp. 95-106.

Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf (2015). Exponential Lower Bounds for Polytopes in Combinatorial Optimization. *Journal of the ACM* 62:2, Article No. 17.

Martin, R.K. (1991) Using separation algorithms to generate mixed integer model reformulations. *Operations Research Letters* 10:3, pp.119–128.

Yannakakis, M. (1991). Expressing combinatorial optimization problems by linear programming. *Journal of Computer and System Sciences* 43:3, pp. 441-466.