271
правка
Изменения
Нет описания правки
<tex> P/poly \subset </tex> схемная сложность полином.
|proof=
Пусть <tex> L \in P/poly </tex>. Тогда существуют <tex> a_0, a_1, .. , a_n, .. </tex> {{---}} подсказки. Зафиксируем n. Пусть подсказка <tex> a_n </tex> позволяет определить, удовлетворяет ли вход x длины n логической схеме. Зашьем эту подсказку в логическую схему <tex> C_n </tex>. Теперь логическая схема допускает удовлетворяет только словам из языка.
}}
