分離問題

【ぶんりもんだい (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} }\,$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.