Изменения
Нет описания правки
|definition=
<tex>P/poly=\{L | \forall n </tex> существует логическая схема <tex> C_n </tex> с <tex> n </tex> входами и одним выходом такая, что:
#размеры <tex> C_n \leqslant p(n)</tex>, где <tex> p </tex> {{---}} полином;
#<tex>x \in L \iff C_{|x|}(x) = 1 \}</tex>.
}}
<tex> P/poly \subset </tex> схемная сложность полином.
|proof=
Пусть <tex> L \in P/poly </tex>. Тогда существуют <tex> a_0, a_1, .. , a_n, .. </tex> {{---}} подсказки. Зафиксируем n. Числу соответствует логическая схема <tex> C_n </tex>. Запишем программу p в виде логической схемы, которая принимает на вход слово длины n и подсказку <tex> a_n </tex>, за счет чего распознаваться будут только слова из языка. А теперь зашьем Зашьем подсказку в самой схеме. Теперь схема , теперь она принимает только слова длины n и определяет их принадлежность языку.
}}
