证明停机问题是NP难问题的方法？

Question

在关于NP、NP-hard和NP-complete定义的一个问题的这个回答中，Jason声称：停机问题是经典的NP-hard问题。这个问题给定一个程序P和输入I，它是否会停止？这是一个判定问题，但它不属于NP。很明显，任何NP-complete问题都可以归约到这个问题。

尽管我认为停机问题在直觉上比NP中的任何问题都要难得多，但我无法得出一个形式化、数学上的证明，证明停机问题是NP-hard问题。特别地，我似乎找不到一个多项式时间的一对多映射，将每个NP问题（或者至少是任何已知的NP-complete问题）的实例归约到停机问题上。

有没有一个简单的证明表明停机问题是NP-hard问题呢？

- templatetypedef

Answer 1

我们首先需要注意的是，所有NP完全问题都可以归约为3SAT问题。现在我们有一个图灵机，它迭代所有可能的赋值，如果找不到满足条件的解，则会一直运行下去。当且仅当3SAT实例可满足时，该机器才会停止。

完成证明 - 我们可以在多项式时间内将任何NP完全问题的实例都归约为3SAT问题。从那里，我们可以通过将输入与上述图灵机的描述（大小为常数）配对来将此问题归约为停机问题。由于图灵机的大小只是常数级别，因此这种配对可以在多项式时间内完成。然后，原始的NP完全问题的答案是“是”，当且仅当3SAT实例可满足，当且仅当所给定的输入能使图灵机停机。

- Watson Ladd

---

非常感谢！我错过了引入解决问题的TM的中间步骤。 - templatetypedef

停机问题众所周知是不可判定的，那么如何可能存在一个算法在NP完全时间内决定它？ - djhaskin987

@djhaskin987 停机问题不是NP完全问题（因为它不可判定，因此不属于NP），但它是NP难问题（也就是说，在多项式时间约简后，至少与NP中的所有问题一样困难），因为每个决策问题都可以归约到它。 - Richard Smith

我不清楚如何在多项式时间内将3SAT降低到HP，因为迭代是指数级的。 - idelvall

仅减少本身——也就是构建迭代所有赋值的图灵机——必须在多项式时间内运行。解决你所减少的问题（即让图灵机运行）不需要是多项式时间。 - David Südholt