Схемная сложность

Пусть [math]\Sigma = \{0, 1\}[/math].
Тогда язык [math]L[/math] имеет схемную сложность [math]f(n)[/math], если [math]\exists c_1, c_2, \ldots c_n, \ldots [/math] - логические схемы, такие что

1. [math]c_i[/math] имеет [math]i[/math] входов и один выход
2. количество логических элементов в схеме [math]c_i[/math] равно [math]|c_i| \le f(i)[/math]
3. [math]\forall x ~c_{|x|}(x) = 1 \Leftrightarrow x \in L [/math]

Утверждение

Если [math] L \in DTIME(f(n))[/math], то [math]L[/math] имеет схемную сложность [math]O(f(n)^2)[/math]

Следствие

Обозначим P\poly [math] = \{L | L [/math] имеет схемную сложность полином[math]\}[/math]
Тогда [math] P \subset [/math] P\poly