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

Question

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

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

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

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

Answer 1

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

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