Complejidad de la extensión

---

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

La complejidad de la extensión depende de la forma precisa de , no solo de su estructura combinatoria. Por ejemplo, los polígonos regulares con lados tienen una complejidad de extensión (expresada usando la notación O grande ), ^{[4] [5]} pero algunos otros polígonos convexos tienen una complejidad de extensión al menos proporcional a . ^[5]${\ estilo de visualización P}$${\ estilo de visualización n}$${\displaystyle O(\log n)}$${\ estilo de visualización n}$${\ estilo de visualización {\ sqrt {n}}}$

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 usarse potencialmente para diseñar algoritmos eficientes para el problema, usando programación lineal en su formulación extendida. Por este motivo, los investigadores han estudiado la complejidad de extensión de los politopos que surgen de esta forma. ^[6] Por ejemplo, se sabe que el politopo coincidente tiene una complejidad de extensión exponencial. ^[7] Por otro lado, el politopo independiente de matroides regulares tiene complejidad de extensión polinomial. ^[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]}

---