Показать, что <m>P/poly</m> содержит некоторые невычислимые функции.
Показать, что <m>P/poly</m> содержит некоторые невычислимые функции.
−
[[Category:На проверку]]
+
[[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> содержит невычислимые функции.
+
Версия 01:51, 26 декабря 2014
Показать, что содержит некоторые невычислимые функции.