離散分離定理

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

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