为什么 NP 问题不能用确定性图灵机解决，但是每个 NTM 都有 TM
Why NP problem can not be solved using deterministic Turing machine, however every NTM has TM
因为每个非确定性图灵机都有一个等效的确定性图灵机。
为什么我们不能使用确定性 TM 解决 NP 问题？
In the second construction, the constructed DTM effectively performs a breadth-first search of the NTM's computation tree, visiting all possible computations of the NTM in order of increasing length until it finds an accepting one. Therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is believed to be a general property of simulations of NTMs by DTMs. The P = NP problem, the most famous unresolved question in computer science, concerns one case of this issue: whether or not every problem solvable by a NTM in polynomial time is necessarily also solvable by a DTM in polynomial time.
换句话说，当您将 NTM 转换为相应的 DTM 时，对于 NP 问题，您的解决方案的算法复杂度将呈指数级增长。
如果你能证明不是这样（对于任何NP问题），恭喜你，你已经证明了P=NP。
因为每个非确定性图灵机都有一个等效的确定性图灵机。 为什么我们不能使用确定性 TM 解决 NP 问题？
In the second construction, the constructed DTM effectively performs a breadth-first search of the NTM's computation tree, visiting all possible computations of the NTM in order of increasing length until it finds an accepting one. Therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is believed to be a general property of simulations of NTMs by DTMs. The P = NP problem, the most famous unresolved question in computer science, concerns one case of this issue: whether or not every problem solvable by a NTM in polynomial time is necessarily also solvable by a DTM in polynomial time.
换句话说，当您将 NTM 转换为相应的 DTM 时，对于 NP 问题，您的解决方案的算法复杂度将呈指数级增长。
如果你能证明不是这样（对于任何NP问题），恭喜你，你已经证明了P=NP。