離散分離定理

出典: ORWiki

【りさんぶんりていり (discrete separation theorem)】

一般に, あるクラスに属する関数 $f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ +\infty \}\,$ と $g: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ -\infty \}\,$ が $f(x) \geq g(x)\,$ $(\forall \ x \in {\mathbf Z}^{n})\,$ を満たすならば, ある $\alpha \in {\mathbf Z}\,$ , $p \in {\mathbf Z}^{n}\,$ が存在して $f(x) \geq \alpha + \langle p, x \rangle \geq g(x) \qquad (\forall \ x \in {\mathbf Z}^{n})\,$ が成り立つ,という形の定理を離散分離定理という. ここで, $\textstyle \langle p, x \rangle = \sum_{i=1}^{n}p_{i}x_{i}\,$ であり, $p\,$ が整数ベクトルに選べることが離散性の反映である.