Extension complexity: Difference between revisions

Revision as of 07:12, 4 September 2021

Revision as of 16:47, 19 January 2023

Line 1:

In [[convex geometry]] and [[polyhedral combinatorics]], the '''extension complexity''' isof a [[convex polytope]] <math>P</math> is the smallest number of [[Facet (geometry)|facets]] among convex polytopes <math>Q</math> that have <math>P</math> as a projection. In this context, <math>Q</math> is called an '''extended formulation''' of <math>P</math>; it may have much higher dimension than <math>P</math>.{{r|balas|kaibel|ccz}}

The extension complexity depends on the precise shape of <math>P</math>, not just on its combinatorial structure. For instance, [[regular polygon]]s with <math>n</math> sides have extension complexity <math>O(\log n)</math> (expressed using [[big O notation]]),{{r|btn|frt}} but some other convex <math>n</math>-gons have extension complexity at least proportional to <math>\sqrt{n}</math>.{{r|frt}}