分離問題

出典: ORWiki

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

凸集合 $P \subseteq {\mathbf R}^n\,$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\mathbf R}^n\,$ に対して $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\,$ および $b \in {\mathbf R}\,$ を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.