为何NP问题无法用确定性图灵机求解，尽管每个NTM都存在等价TM

首先要明确一个核心误区：NTM和TM的等价是可计算性层面的等价，和复杂度层面的等价完全是两回事，这就是问题的核心矛盾点。

• 可计算性范畴的「等价」定义非常宽松：只要存在任意一台TM，能在有限时间内（不管这个有限时间有多长）得到和NTM完全一致的判定结果，就算二者等价，完全不限制时间开销的量级。我们说所有NTM都有等价TM，指的就是这个层面的等价。
• 而NP问题的定义是时间复杂度绑定的：它特指可以在多项式时间内被NTM判定的问题类，我们日常说的「求解NP问题」，默认指的是在多项式时间内完成求解，也就是符合P类问题的判定标准。
• 目前确定性TM模拟NTM的通用方法，是穷举NTM所有可能的非确定性分支，每一步的分支数如果是k，n步就会产生k^n个分支，时间复杂度直接达到指数级，远远达不到多项式时间的要求。

举个简单的例子：子集和问题是典型的NP问题，NTM可以为每个元素单独开一个分支决定选或不选，每个分支只需要O(n)时间就能验证子集和是否符合要求，整体NTM的运行时间是多项式级的。换成确定性TM的话，你只能逐个遍历所有2^{n个可能的子集，当n=100时，2}100次运算就算是当前最强的超级计算机也要跑上万亿年，根本不具备实际求解的可行性。

最后要澄清一点：我们不是完全无法用确定性TM求解NP问题，暴力穷举当然能得到正确结果，只是目前没有找到任何通用的多项式时间确定性解法，这个问题的本质就是千禧年七大难题之一的「P vs NP问题」，至今没有被证明或证伪。

内容的提问来源于stack exchange，提问作者Ahmed_A