Схема - описание вычислений

• Орграф без циклов
• Вершины помечены как in, out или И, ИЛИ, НЕ
• Входная степень равна числу операндов

Сложность схемы $C$ (обозн. $|C|$) равна числу функциональных элементов

Полиномиальная вычислимость

Функция $f: \mathbb{B}^* \rightarrow \mathbb{B}^*$ полиномиально вычислима, если существуют ${C_n}$ и полином $p$ такие, что $\forall n$ схема $C_n$ вычисляет $f|_{\mathbb{B}^n}$, и $|C_n| \leq p(n)$