分離問題

提供: ORWiki
2007年7月14日 (土) 01:39時点における222.225.128.209 (トーク)による版
ナビゲーションに移動 検索に移動

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

凸集合 が与えられているとする. このとき, 任意のベクトル に対して か否かを判定し, ならば, を分離する不等式を求める, すなわち かつ なる および を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.