Схемная сложность и класс P/poly

Определения

Определение:

$P/poly=\{L | \forall n$ существует логическая схема $C_n$ с $n$ входами и одним выходом такая, что: размеры $C_n \leqslant p(n)$; $x \in L \iff C_{|x|}(x) = 1 \}$.

Определение:

Пусть C — сложностный класс, f — функция. Тогда $C/f = \{L|$ существуют $a_0, a_1, .. , a_n, .. ,$ программа p, удовлетворяющая ограничениям C: $|a_i| \leqslant f(i)$; $x \in L \iff p(x, a_{|x|})=1$.

Определение:

Пусть $F = \{f_i\}$. Тогда $C/F = \bigcup\limits_{f \in F} C/f$.

Теоремы

Теорема:

$P \subset P/poly$.

Доказательство:

$\triangleright$

$L \in P \Rightarrow \exists$ Машина Тьюринга m такая, что $L(m)=L$. В теореме Кука мы показали, что для машины Тьюринга можно составить логическую схему. Отсюда следует, что $P \subset P/poly$.

$\triangleleft$