Участник:AlexeyKhrabrov/P\poly contains unsolvable — Решение Храбров

Материал из DISCOPAL
Перейти к: навигация, поиск

Будем использовать определение класса P/poly через МТ с подсказками. Переформулируем задачу в терминах языков: показать, что P/poly содержит неразрешимые языки.
Пусть L из {0, 1}* - неразрешимый язык. Построим по нему язык L' = {1n, если двоичная запись n лежит в L}. L' - неразрешим, т.к. иначе L был бы разрешим. Докажем, что L' лежит в P/poly.
Возьмем в качестве подсказки для для слова x 1, если слово длины |x| содержится в L', иначе 0. Тогда можно построить МТ которая по слову x и подсказке для слов длины |x| проверяет, что x состоит только из 1 (за полиномиальное время), и если это так, выдает значение подсказки, иначе выдает 0. Получаем полиномиальную МТ, принимающую язык L' по подсказке полиномиальной длины, зависящей только от длины входа. Значит, L' лежит в P/poly, но при этом является неразрешимым. Как смотреть многопоточное MKV-видео