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