}}
{{ТеоремаЛемма
|statement=
Любой унарный язык принадлежит <tex> \mathrm{P/poly} </tex> содержит неразрешимые языки.
|proof=
Пусть Рассмотрим произвольный унарный язык <tex> L \subset \{0, 1\}^* </tex> {{---}} произвольный неразрешимый язык. Пусть Подсказкой для слова <tex> A = \{1^n | x </tex> бинарное представление будет единица, если слово длины <tex> n |x| </tex> принадлежит есть в <tex> L \} </tex>, иначе ноль. Машина Тьюринга получит на вход слово <tex> \mathrm{P/poly} </tex> позволяет разрешить <tex> A </tex>. В качестве подсказки <tex> a_n x </tex> и подсказку для входа слов длины <tex> |x | </tex> будем передавать единицу. Теперь произведем проверку, если что <tex> 1^n \in A x </tex>действительно из нашего унарного алфавита. Если это не так, иначе ноль. <br>Язык <tex> A </tex> неразрешимто сразу же не допустим слово, иначе можно было бы разрешить и <tex> L </tex>, что неверновыведем значение подсказки. <br>Таким образом, любой унарный язык принадлежит <tex> \mathrm{P/poly} </tex> содержит неразрешимые языки.
}}
{{Теорема
|statement=
<tex> \mathrm{P} \ne \mathrm{P/poly} </tex>содержит неразрешимые языки.
|proof=
Это следует из предыдущей теоремыРассмотрим произвольный неразрешимый язык <tex> L \subset \{0, 1\}^* </tex>. Построим язык <tex> A </tex> следующим образом: <tex> A = \{ 1^n | </tex> бинарное представление <tex> n </tex> принадлежит <tex> L \} </tex>. Унарный язык <tex> A \in \mathrm{P/poly} </tex>, но то же время <tex> A </tex> неразрешим, иначе можно было бы разрешить <tex> L </tex>. <br>Получается, что <tex> \mathrm{P/poly} </tex> содержит неразрешимые языки.
}}
[[Категория: Теория сложности]]
