Рассмотрим язык $E_{tm}={ \langle M \rangle: M\text{является машиной Тьюринга, которая ничего не принимает}$
Я не уверен, как даже начать. Моя идея состоит в том, чтобы обеспечить сокращение времени полигонов из некоторой задачи NP - Complete. E_tm
Чего я не понимаю, так это того, что, зная, что E_tm неразрешим, но класс NP-Hard разрешим.
решение:
Д.Ф.: Проблема является NP-сложной, если все проблемы в NP сводятся к ней за полиномиальное время, даже если она может и не быть в самой NP (стр. 326 Сипсер) (единственное определение, которое есть в нашей книге). Для любого языка L', находящегося в NP, если мы покажем, что мы можем поливременно свести его к Etm. Это докажет, что Etm является NP-жестким. Поскольку L' находится в NP по определению, существует TM (NTM, но поскольку они эквивалентны по мощности, я пишу TM) M' такое, что решает L'.
TM M'' that takes as an input <M,w> constructs
TM M' such that
on arbitrary x
if w = x
run M on w if accept => reject
if reject => accept
else reject.
Следовательно, M принимает w тогда и только тогда, когда M'' отвергает все входные данные. Давайте подтвердим это. Сначала предположим, что M принимает w, затем M'' отклоняет любой вход, поэтому L(M'') = пусто. Теперь предположим, что M отвергает w, тогда M'' принимает, поэтому L(M'') не пусто. Обратите внимание, что для построения M'' требуется полиномиальное время. Это завершает доказательство.
