拡張複雑度

凸幾何学および多面体組み合わせ論において、凸多面体の拡張複雑度は${\displaystyle P}$凸多面体の中で面の数が最も少ない。${\displaystyle Q}$持っている${\displaystyle P}$投影として。この文脈では、${\displaystyle Q}$拡張された定式化と呼ばれる${\displaystyle P}$; 次元は、${\displaystyle P}$[ ^{1 ] [ 2 ] [ 3 ]​}

拡張の複雑さは、${\displaystyle P}$組み合わせ構造だけではなく。例えば、正多角形は${\displaystyle n}$側面は拡張複雑性を持つ${\displaystyle O(\log n)}$（ビッグオー記法で表現）^{[ 4 ] [ 5 ]}しかし他の凸関数もある${\displaystyle n}$-角形の拡張複雑度は少なくとも に比例する${\displaystyle {\sqrt {n}}}$[ ^{5 ]​}

組み合わせ最適化問題の実行可能な解を表す多面体の拡張複雑性が低い場合、その拡張定式化に対して線形計画法を用いることで、問題に対する効率的なアルゴリズムを考案できる可能性がある。このため、研究者たちはこのようにして生じる多面体の拡張複雑性を研究してきた。^{[ 6 ]}例えば、マッチング多面体は指数関数的な拡張複雑性を持つことが知られている。^{[ 7 ]}一方、正則マトロイドの独立多面体は多項式的な拡張複雑性を持つ。^{[ 8 ]}

拡張複雑性の概念は、多面体の射影の代わりにスペクトラヘドラの射影を考慮することにより、線形計画法から半正定値計画法に一般化されている。 ^{[ 9 ] [ 10 ]}