CNFとかDNFといった述語表現の新しいものとして、決定リストというものを導入する. 深さが \(k\) の決定リストを k-DL とかく.
k-CNF, k-DNF とその表現力を比較していく.
k-CNF は一つの節にリテラルな \(k\) 個あるやつ.
k-clause-CNF は節が \(k\) 個あるやつ.
変数が \(n\) 個 (そのnotも入れると \(2n\) 個) としたものを k-CNF(n) みたいに \((n)\) を添えて書く.
連言で高々 \(k\) 個の変数が連なる節として あり得るもの全てを \(C^n_k\) と書く. これの大きさは、 \(2n\) から高々 \(k\) 個選ぶ通りだから、
\[\sum_{i=0}^k \binom{2n}{i} \in O(n^k)\]次のような二分木を決定木と呼ぶ
次のように決定木は一つの述語として働く. ノードにラベルされた変数が0であるか1であるかについて左か右の枝を、 根から辿ってく. 葉にたどり着いたらそのラベルが述語の値.
深さ \(k\) の決定木 k-DT.
決定リストとは、次のようなペアのリストである:
\[(f_1, v_1), \cdots, (f_r, v_r)\]ここで、 \(f_j\) は \(C^n_k\) の要素である. つまり and で連なった変数列であり、述語として働く. \(v_j\) は \(0\) または \(1\) である.
これがどのように述語として働くかと言うと、
\[\text{if } f_1(x) \text{ then } v_1 \text{ elsif } f_2(x) \text{ then } v_2 \text{ elsif } \cdots\]です.
ちゃんと完全関数とするためには、最後の \(f_r\) は \(true\) でないといけない.
CNFなんかと違って決定リストは否定を簡単に決定リストとして構成することができる. つまり閉じている.
\(k < n\) のとき、k-CNF(n) や k-DNF(n) は k-DL(n) の真の部分集合である. つまり決定リストとして表現し直すことができる.
\(k < n\) のとき、 k-DT(n) は k-DL(n) の真の部分集合.