Extension complexity
Extension complexity is a measure of the minimum number of linear inequalities required to represent a polytope as the linear image of another polyhedron. The representing polyhedron is called an extended formulation, and its additional coordinates are auxiliary variables that disappear under projection. Extension complexity therefore measures descriptive complexity after arbitrary linear lifting rather than in the original coordinate space.
For a polytope (P\subseteq\mathbb{R}^d), an extended formulation consists of a polyhedron
[ Q={(x,y)\in\mathbb{R}^{d+k}: Ex+Fy\leq g} ]
whose projection onto the (x)-coordinates is exactly (P). Equivalently,
[ P={x\in\mathbb{R}^d:\exists y\in\mathbb{R}^k,\ Ex+Fy\leq g}. ]
The size of this formulation is the number of inequalities in the description of (Q); linear equations are not counted because they can be eliminated or represented without changing the central complexity measure. The extension complexity (\operatorname{xc}(P)) is the minimum size among all extended formulations of (P).
Geometric interpretation
A polytope can have many facets in its original space while possessing a substantially smaller description in a higher-dimensional space. Projection may transform a polyhedron with comparatively few facets into one with a much larger facial structure. Extension complexity records the smallest number of facets needed before this projection occurs.
A standard example is the permutahedron. Its direct facet description contains exponentially many inequalities, but it admits polynomial-size extended formulations derived from sorting networks and related constructions. The additional variables encode intermediate comparisons, while projection retains only the coordinates of the permutahedron itself.
Every polytope with (N) vertices has an extended formulation with at most (N) nonnegativity inequalities. One introduces a coefficient for each vertex, requires the coefficients to form a convex combination, and projects the resulting simplex onto the original polytope. This general construction is often much larger than formulations that exploit the polytope’s combinatorial structure.
Slack matrices and nonnegative factorization
The main algebraic characterization of extension complexity uses the slack matrix. Suppose that
[ P={x\in\mathbb{R}^d:Ax\leq b} ]
and that (v_1,\ldots,v_N) are the vertices of (P). The slack matrix (S) has one row for each chosen facet inequality and one column for each vertex, with entries
[ S_{ij}=b_i-A_i v_j. ]
Each entry measures the distance from a vertex to a supporting hyperplane in the affine scale determined by the corresponding inequality. The zero pattern records the vertex–facet incidence relation, while the positive values contain additional metric information.
The nonnegative rank of a nonnegative matrix (S), written (\operatorname{rank}_+(S)), is the least integer (r) for which there exist nonnegative matrices (T) and (U) satisfying
[ S=TU, ]
where (T) has (r) columns and (U) has (r) rows. Mihalis Yannakakis established the factorization theorem identifying the extension complexity of a polytope with the nonnegative rank of its slack matrix, subject to the standard conventions for degenerate and lower-dimensional polytopes:
[ \operatorname{xc}(P)=\operatorname{rank}_+(S). ]
The theorem converts a geometric minimization problem into a matrix-factorization problem. A small extended formulation produces a low-rank nonnegative factorization by expressing each facet slack through the inequalities of the extension. Conversely, a nonnegative factorization supplies auxiliary variables from which an extended formulation can be constructed.
Ordinary matrix rank gives only a weak lower bound because a (d)-dimensional polytope has a slack matrix of ordinary rank at most (d+1), even when its extension complexity is exponential in (d). The distinction arises from the nonnegativity requirement, which prevents cancellation between factor entries.
Communication-complexity method
Lower bounds on nonnegative rank are closely connected with communication complexity. The row index of a slack matrix can be assigned to one participant and the column index to another. A randomized protocol whose output has the corresponding slack as its expectation yields a nonnegative factorization, while a small factorization yields a protocol of related cost.
This correspondence permits combinatorial properties of the matrix to obstruct compact linear formulations. Rectangle coverings of the support provide elementary bounds, although these bounds depend only on which entries vanish. Stronger methods use the magnitudes of positive entries and analyze how a low-rank nonnegative factorization would distribute weight across selected submatrices.
The unique-disjointness matrix is central to several exponential lower bounds. Suitable submatrices of slack matrices for stable-set and cut polytopes inherit its communication structure. Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf used this connection to establish exponential extension-complexity bounds for several fundamental combinatorial polytopes. Their results showed that the absence of a compact formulation can persist even when no symmetry condition is imposed on the extension.
In 2016, You Watanabe and Kanstantsin Pashkovich developed a normalized-slack formulation of the same method for restricted stable-set constructions. Their analysis made the lower bound invariant under the addition of redundant inequalities and under changes to the affine presentation of the polytope. The resulting formulation remained an application of nonnegative-rank bounds rather than a distinct complexity measure.
Matching and traveling-salesperson polytopes
The matching polytope of a graph is the convex hull of incidence vectors of its matchings. Its direct description involves degree constraints together with inequalities indexed by odd vertex sets. Yannakakis proved an exponential lower bound for symmetric extended formulations of the matching polytope, where symmetry requires graph automorphisms to extend to the lifted representation.
Symmetry restrictions initially left open the possibility that a compact asymmetric formulation existed. Thomas Rothvoß later proved that the matching polytope of the complete graph has extension complexity (2^{\Omega(n)}). The result applies to arbitrary linear extensions and therefore separates the size of the polytope’s smallest linear lift from the efficiency of polynomial-time matching algorithms.
The traveling-salesperson polytope is the convex hull of incidence vectors of Hamiltonian cycles in a complete graph. Exponential lower bounds for related cut and stable-set polytopes transfer to this polytope through affine reductions and face arguments. Consequently, no polynomial-size linear program whose feasible-region projection is exactly the traveling-salesperson polytope can represent all instances.
This statement concerns exact linear descriptions rather than the broader computational complexity of the traveling salesperson problem. An optimization problem can possess a polynomial-time algorithm while its natural solution polytope has exponential extension complexity, as demonstrated by matching. Conversely, large extension complexity does not by itself establish an unconditional lower bound for every algorithmic model.
Faces, projections, and reductions
Extension complexity behaves monotonically under several geometric operations. If (F) is a face of (P), then an extended formulation for (P) can be intersected with the equation defining (F), giving
[ \operatorname{xc}(F)\leq \operatorname{xc}(P). ]
If (R) is a linear projection of (P), the same extension can be followed by the additional projection, so
[ \operatorname{xc}(R)\leq \operatorname{xc}(P). ]
These relations support reductions between polytope families. To transfer a lower bound from (R) to (P), it is sufficient to realize (R) as a projection of a face of (P). Such reductions preserve exact representability while avoiding dependence on a particular inequality description.
Cartesian products also interact predictably with extended formulations. Formulations for two factors can be combined to produce a formulation for their product whose size is the sum of the two original sizes. Lower bounds for products require additional analysis because a minimum extension need not decompose according to the visible product structure.
Symmetric extension complexity
A symmetric extended formulation respects a prescribed group action on the original polytope. Each symmetry of the polytope acts compatibly on the variables and inequalities of the extension. Symmetric extension complexity is the minimum size under this restriction and can exceed unrestricted extension complexity.
The distinction is mathematically substantive because compact formulations often introduce auxiliary coordinates that do not transform in the same manner as the original variables. Yannakakis’s early matching lower bound applied to symmetric formulations, whereas later nonnegative-rank arguments removed the symmetry requirement. For other polytope families, symmetric and unrestricted formulations continue to have different known bounds.
Approximate formulations
An approximate extended formulation represents a polytope lying between a target feasible region and a controlled relaxation of that region. Its size measures how many inequalities are needed to reproduce specified approximation guarantees under linear optimization.
The slack-matrix framework extends to approximation by replacing the exact slack matrix with matrices compatible with the allowed relaxation. Lower bounds then depend on how much the relevant communication matrix can be perturbed before its nonnegative rank decreases. This framework distinguishes exact geometric representation from approximation schemes whose feasible regions contain additional points.
Approximate extension complexity remains specific to linear lifts. More general lifts replace the nonnegative orthant with another convex cone. Semidefinite extension complexity, for example, is governed by positive-semidefinite factorizations rather than nonnegative factorizations and can differ substantially from linear extension complexity.
Relation to optimization
A polynomial-size extended formulation permits linear optimization over the represented polytope through linear programming in the lifted variables. The converse does not hold: polynomial-time optimization does not imply a polynomial-size extended formulation. The matching polytope provides the standard separation because matching is polynomial-time solvable while the polytope has exponential extension complexity.
Extension complexity is also nonuniform. A bound may provide a separate formulation for each dimension without supplying an efficient algorithm that constructs those formulations. Conversely, an algorithm may optimize through separation, dynamic programming, or another representation that is not the projection of a small linear system.
The measure therefore concerns the representational power of linear inequalities under projection. It does not serve as a general measure of algorithmic difficulty, although it supplies lower bounds for algorithms whose operation requires a compact exact linear formulation.