分離問題

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

凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$ に対して$x_* \in P$ か否かを判定し, $x_* \not\in P$ならば, $P$ と $x_*$ を分離する不等式を求める, すなわち$a^{\rm T} x \leq b$ $(\forall x \in P)$ かつ$a^{\rm T} x_* > b$ なる $a \in {\bf R}^n$ および $b \in {\bf R}$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.