证明暂停问题对NP不利吗? [英] Proof that the halting problem is NP-hard?

问题描述

在此问题的答案中NP，NP-hard和NP-complete的定义，Jason声称

In this answer to a question about the definitions of NP, NP-hard, and NP-complete, Jason makes the claim that

停顿问题是经典的NP难题.这是给定程序P和输入I会停止的问题吗?这是一个决策问题，但不是NP问题.显然，任何NP完全问题都可以简化为这个问题.

The halting problem is the classic NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one.

虽然我同意暂停问题在直观上比NP中的任何问题都要困难"得多，但老实说，我无法提出形式上的数学证据来证明暂停问题是NP难题.特别是，我似乎找不到从NP中每个问题(或至少任何已知的NP完全问题)到停止问题的多项式时间多对一映射.

While I agree that the halting problem is intuitively a much "harder" problem than anything in NP, I honestly cannot come up with a formal, mathematical proof that the halting problem is NP-hard. In particular, I cannot seem to find a polynomial-time many-to-one mapping from instances of every problem in NP (or at least, any known NP-complete problem) onto the halting problem.

是否有直接证据表明停止问题是NP难题?

推荐答案

我们首先注意到，所有NP完全问题都可以归结为3SAT.现在，我们有了一个图灵机，可以遍历所有可能的分配，如果找不到令人满意的分配，那么它将永久运行.当且仅当3SAT实例可满足时，该机器才会暂停.

We begin by noting that all NP-complete problems are reducible to 3SAT. Now we have a Turing machine that iterates over all possible assignments, and if a satisfying assignment is not found then it runs forever. This machine halts if and only if the 3SAT instance is satisfiable.

完成证明-我们可以在多项式时间内将NP完全问题的任何实例简化为3SAT.从那里，我们可以通过将输入与上述图灵机的描述(大小固定)配对来将这个问题简化为停顿问题的一个实例.这种配对可以在多项式时间内完成，因为图灵机只有固定的大小.然后，如果图灵机在给定输入上停止，则3SAT实例是可以满足的，则原始NP完全问题的答案为是".

Completing the proof - we can, in polynomial time, reduce any instance of an NP-complete problem to 3SAT. From there, we can reduce this problem to an instance of the halting problem by pairing the input with a description of the Turing machine described above (which has constant size). This pairing can be done in polynomial time, because the Turing machine has only constant size. Then, the original NP-complete problem has answer "yes" iff 3SAT instance is satisfiable iff the Turing machine halts on the given input.

这篇关于证明暂停问题对NP不利吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！