分離問題

【ぶんりもんだい (separation problem)】

凸集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P \subseteq {\mathbf R}^n\,} が与えられているとする. このとき, 任意のベクトル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_* \in {\mathbf R}^n\,} に対して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_* \in P\,} か否かを判定し, $x_{*}\not \in P\,$ならば, $P\,$ と $x_{*}\,$ を分離する不等式を求める, すなわち$a^{\mathrm {T} }x\leq b\,$ $(\forall x\in P)\,$ かつ$a^{\rm {T}}x_{*}>b\,$ なる $a\in {\mathbf {R} }^{n}\,$ および 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b \in {\mathbf R}\,} を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.