Полиномиальная иерархия/Задачи/P\poly contains unsolvable — различия между версиями

Текущая версия на 06:50, 4 мая 2023

Показать, что содержит некоторые невычислимые функции.

@@ Строка 1: / Строка 1: @@
 Показать, что <m>P/poly</m> содержит некоторые невычислимые функции.
-[[Category:На проверку]]
+[[Категория:Решенные задачи]]
+[[Категория:Теоретические задачи]]
-===Остапенко Максим, 975 группа.===
-Переформулируем задачу в эквивалентную форму:
-Класс <m>P/poly</m> содержит неразрешимые языки.
-Действительно, если язык <latex>$L$</latex> - неразрешим, то предикат <latex>$f(x) = 1$ ,  $x \in L$, 0 иначе</latex>, невычислим.
-Рассмотрим произвольный неразрешимый язык <latex>L \subset \{0, 1\}^*</latex>. Построим язык A следующим образом: <latex>A = \{ 1^n </latex>| бинарное представление <latex>n</latex> принадлежит<latex> L\}</latex>. Язык <latex>A \in \mathrm{P/poly}</latex>, но то же время A неразрешим, иначе можно было бы разрешить <latex>$L$</latex>.
-Получается, что <latex>\mathrm{P/poly}</latex> содержит неразрешимые языки.
-Значит <m>P/poly</m> содержит невычислимые функции.