Complejidad de la extensión

En geometría convexa y combinatoria poliédrica , la complejidad de extensión de un politopo convexo${\displaystyle P}$es el número más pequeño de facetas entre los politopos convexos.${\displaystyle Q}$que tienen${\displaystyle P}$como una proyección. En este contexto,${\displaystyle Q}$se denomina una formulación extendida de${\displaystyle P}$; puede tener una dimensión mucho mayor que${\displaystyle P}$. ^{[ 1 ] [ 2 ] [ 3 ]}

La complejidad de la extensión depende de la forma precisa de${\displaystyle P}$, no solo en su estructura combinatoria. Por ejemplo, polígonos regulares con${\displaystyle n}$Los lados tienen complejidad de extensión${\displaystyle O(\log n)}$(expresado usando la notación de la gran O ), ^{[ 4 ] [ 5 ]} pero alguna otra convexa${\displaystyle n}$Los -gons tienen una complejidad de extensión al menos proporcional a${\displaystyle {\sqrt {n}}}$. ^{[ 5 ]}

Si un politopo que describe las soluciones factibles a un problema de optimización combinatoria tiene una baja complejidad de extensión, esto podría utilizarse para diseñar algoritmos eficientes para el problema, empleando programación lineal en su formulación extendida. Por esta razón, los investigadores han estudiado la complejidad de extensión de los politopos que surgen de esta manera. ^{[ 6 ]} Por ejemplo, se sabe que el politopo de emparejamiento tiene una complejidad de extensión exponencial. ^{[ 7 ]} Por otro lado, el politopo de independencia de matroides regulares tiene una complejidad de extensión polinómica. ^{[ 8 ]}

La noción de complejidad de extensión también se ha generalizado de la programación lineal a la programación semidefinida , al considerar proyecciones de espectroedros en lugar de proyecciones de politopos. ^{[ 9 ] [ 10 ]}