271
правка
Изменения
→Теоремы
Пусть <tex> A = \{1^n | </tex> бинарное представление <tex> n </tex> принадлежит <tex> L \} </tex>.
<tex> \mathrm{P/poly} </tex> позволяет разрешить <tex> A </tex>. В качестве подсказки <tex> a_n </tex> для входа <tex> x </tex> будем передавать единицу, если <tex> 1^n \in A </tex>, иначе ноль. <br>
Язык <tex> A </tex> неразрешим, иначе можно было бы разрешить и <tex> L </tex>, что неверно. <br>
Таким образом, <tex> \mathrm{P/poly} </tex> содержит неразрешимые языки.
}}
[[Категория: Теория сложности]]
