Изменения

Пусть <tex> L \in P/poly </tex>, x {{---}} входная строка. Тогда для L существуют подсказки <tex> a_0, a_1, .. , a_n, .. </tex>. Программа p по входу x и подсказке <tex> a_{|x|} </tex> определяет принадлежность x языку L. Зафиксируем длину входной строки x как n. Запишем p в виде логической схемы <tex> C_{C_m </tex> ( <tex> m = n + |ma_n|} </tex>), которая принимает на вход слова длины n и подсказку <tex> a_n </tex>, <tex> m = n + |a_n| </tex>. Зашьем подсказку в самой схеме. Получим схему <tex> C_n </tex>, принимающую слова длины n и определяющую их принадлежность языку L.