Полиномиальная иерархия/Задачи/P\poly contains unsolvable — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 3: | Строка 3: | ||
Показать, что <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> содержит невычислимые функции. | ||
Версия 13:20, 1 декабря 2014
Показать, что содержит некоторые невычислимые функции.
Остапенко Максим, 975 группа.
Переформулируем задачу в эквивалентную форму:
Класс содержит неразрешимые языки.
Действительно, если язык - неразрешим, то предикат , невычислим.
Рассмотрим произвольный неразрешимый язык . Построим язык A следующим образом: | бинарное представление принадлежит. Язык , но то же время A неразрешим, иначе можно было бы разрешить .
Получается, что содержит неразрешимые языки.
Значит содержит невычислимые функции.