縮約

$X$ を入力の集合、$\varphi$ を性質とする。縮約関数とは、各 $x \in X$ に $X$ の元の有限の列 $\mathrm{shr}(x)$（縮約の候補）を対応させる写像をいう。反例 $x_0$ から始める貪欲な縮約とは、次の手続きをいう: $x_i$ の候補 $\mathrm{shr}(x_i)$ を列の順に調べ、最初に見つかった反例を $x_{i+1}$ として繰り返す。候補の中に反例がなければ $x_i$ を返して止まる。

反例 $x$ が局所的に最小であるとは、$\mathrm{shr}(x)$ の中に反例がないことをいう。写像 $m : X \to \{0, 1, 2, \ldots\}$ が、すべての $x$ とすべての候補 $y \in \mathrm{shr}(x)$ について $m(y) \lt m(x)$ を満たすとき、$m$ を縮約の尺度という。