Extension complexity

In convex geometry and polyhedral combinatorics, the extension complexity of a convex polytope ${\displaystyle P}$ is the smallest number of facets among convex polytopes ${\displaystyle Q}$ that have ${\displaystyle P}$ as a projection. In this context, ${\displaystyle Q}$ is called an extended formulation of ${\displaystyle P}$; it may have much higher dimension than ${\displaystyle P}$.[1][2][3]

The extension complexity depends on the precise shape of ${\displaystyle P}$, not just on its combinatorial structure. For instance, regular polygons with ${\displaystyle n}$ sides have extension complexity ${\displaystyle O(\log n)}$ (expressed using big O notation),[4][5] but some other convex ${\displaystyle n}$-gons have extension complexity at least proportional to ${\displaystyle {\sqrt {n}}}$.[5]

If a polytope describing the feasible solutions to a combinatorial optimization problem has low extension complexity, this could potentially be used to devise efficient algorithms for the problem, using linear programming on its extended formulation. For this reason, researchers have studied the extension complexity of the polytopes arising in this way.[6] For instance, it is known that the matching polytope has exponential extension complexity.[7] On the other hand, the independence polytope of regular matroids has polynomial extension complexity.[8]

The notion of extension complexity has also been generalized from linear programming to semidefinite programming, by considering projections of spectrahedra in place of projections of polytopes.[9][10]