Подтвердить что ты не робот

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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