В ответе на вопрос об определениях NP, NP-жесткого и NP-полного, Джейсон утверждает, что
Остановка проблема - это классическая NP-сложная задача. Это проблема, при которой программа P и ввод I остановятся? Это проблема решения, но ее нет в NP. Ясно, что любая NP-полная проблема может быть сведена к этой.
Хотя я согласен с тем, что проблема остановки интуитивно намного «сложнее», чем что-либо в NP, я, честно говоря, не могу придумать формального математического доказательства что проблема остановки NP-сложна. В частности, мне кажется, что я не могу найти отображение «многие к одному» за полиномиальное время из экземпляров каждой проблемы в NP (или, по крайней мере, любой известной NP-полной проблемы) на проблему остановки.
Есть ли прямое доказательство что проблема остановки является NP-сложной?