Доказательство того, что проблема остановки является NP-трудной?

Question

(Я прошу прощения, если это неправильный сайт для этого вопроса, но, учитывая, что здесь много вопросов теории CS "не так уж сложно для CS", я думаю, что это может подойти. Пожалуйста не стесняйтесь перемещать это, если это неуместно.)

В этом ответе на вопрос об определениях NP, NP-hard и NP-complete Джейсон утверждает, что

Проблема остановки - классическая NP-сложная проблема. Это проблема, при которой программа P и ввод I остановятся? Это проблема решения, но ее нет в NP. Ясно, что любая NP-полная проблема может быть сведена к этой.

Хотя я согласен, что проблема остановки является интуитивно гораздо более сложной проблемой, чем что-либо в NP, я, честно говоря, не могу придумать формального математического доказательства того, что проблема остановки является NP-сложной. В частности, я не могу найти многозначное отображение полиномиального времени от экземпляров каждой проблемы в NP (или, по крайней мере, любой известной NP-полной проблемы) к проблеме остановки.

Есть ли прямое доказательство того, что проблема остановки является NP-трудной?

Answer 1

Начнем с того, что отметим, что все NP-полные задачи сводятся к 3SAT. Теперь у нас есть машина Тьюринга, которая перебирает все возможные назначения, и если удовлетворяющее назначение не найдено, оно выполняется вечно. Эта машина останавливается, если и только если экземпляр 3SAT выполним.

Завершение доказательства - мы можем за полиномиальное время сократить любой случай NP-полной задачи до 3SAT. Оттуда мы можем свести эту проблему к примеру проблемы остановки, сопоставив входные данные с описанием машины Тьюринга, описанной выше (которая имеет постоянный размер). Такое соединение может быть сделано за полиномиальное время, потому что машина Тьюринга имеет только постоянный размер. Затем исходная задача NP-завершения имеет ответ "да", если экземпляр 3SAT выполним, если машина Тьюринга останавливается на заданном входе.