说非确定性图灵机可以在多项式时间内解决 NP 问题会产生什么后果？
这些天我一直在研究NP问题、计算复杂性和理论。我相信我终于掌握了图灵机的概念，但我有一些疑问。
我可以接受，非确定性图灵机对于给定状态和正在读取的符号有几种选择，并且它总是会选择最佳选项，如维基百科所述
NTM 如何“知道”其中哪一个 应该采取什么行动？有两个 看待它的方式。一是说 该机器是“最幸运的” 可能的猜测者”；它总是选择 过渡最终导致 一个接受状态，如果存在这样一个 过渡。另一种是想象 机器“分支”成许多 副本，每份都遵循以下之一 可能的转变。而一个 DTM 具有单一“计算路径” 由此可见，NTM 有一个 “计算树”。如果任何一个分支 树因“接受”而停止 条件，我们说 NTM 接受 输入。
我不明白的是，既然这是一台假想的机器，那么说它可以在多项式时间内解决 NP 问题，我们能得到什么好处呢？我的意思是，我还可以理论化一个神奇的机器，它可以在 O(1) 中解决 NP 问题，如果它可能永远不存在，我能从中得到什么？
提前致谢。
these days I have been studying about NP problems, computational complexity and theory. I believe I have finally grasped the concepts of Turing Machine, but I have a couple of doubts.
I can accept that a non-deterministic turing machine has several options of what to do for a given state and symbol being read and that it will always pick the best option, as stated by wikipedia
How does the NTM "know" which of these
actions it should take? There are two
ways of looking at it. One is to say
that the machine is the "luckiest
possible guesser"; it always picks the
transition which eventually leads to
an accepting state, if there is such a
transition. The other is to imagine
that the machine "branches" into many
copies, each of which follows one of
the possible transitions. Whereas a
DTM has a single "computation path"
that it follows, an NTM has a
"computation tree". If any branch of
the tree halts with an "accept"
condition, we say that the NTM accepts
the input.
What I can not understand is, since this is an imaginary machine, what do we gain from saying that it can solve NP problems in polynomial time? I mean, I could also theorize of a magical machine that solves NP problems in O(1), what do I gain from that if it may never exist?
Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
非确定性图灵机是一个很难掌握的概念。尝试一些其他观点：
不要运行一个可能是最幸运的猜测者的神奇图灵机，而是运行一个更神奇的元机器，在平行宇宙中设置无限数量的随机猜测独立图灵机。每个可能的猜测序列都是在某个宇宙中进行的。如果至少在一个宇宙中机器停止并接受输入，那就足够了：问题实例被设置这些平行宇宙的元机器接受。如果在所有宇宙中机器拒绝或无法停止，元机器就会拒绝该实例。
不要进行任何类型的猜测或分支，而是想象一个人试图说服另一个人该实例应该被接受。第一个人提供非确定性图灵机要做出的一组选择，第二个人检查机器是否接受这些选择的输入。如果是这样，第二个人就会被说服；如果是这样，第二个人就会被说服。如果没有，则第一人失败（这可能是因为该实例无法接受任何选择序列，或者因为第一人选择了糟糕的选择序列）。
忘记图灵机吧。如果一个问题可以用存在主义二阶逻辑中的公式描述，则该问题属于 NP 。也就是说，您采用简单的命题逻辑，允许对命题变量使用任何量词，并允许在开头添加对集合、关系和函数的存在量词。例如，图三色性可以通过从颜色的存在量化开始的公式来描述（节点集）：
<块引用>
∃R∃G∃B
每个节点都必须着色：
<块引用>
∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x)))
并且没有两个相邻节点可以具有相同的颜色 - 称为边关系 E：
<块引用>
∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x))) ∧ (∀ x,y Ø (E(x,y) ∧ ((R(x)) ∧ R(y)) ∨ (G(x) ∧ G(y)) ∨ (B(x) ∧ B(y)))))
二阶变量的存在量化就像一个非确定性图灵机做出完美的猜测。如果您想让某人相信公式 ∃ X (...) 为真，您可以从给出 X 的值开始。多项式时间 NTM 和这些公式不仅“相似”而且实际上等效，这就是费金定理，该定理开创了描述性复杂性领域：复杂性类别不是以图灵机为特征，而是以逻辑公式类别为特征。 忘记图灵机吧
你还说
，是的，你可以。这些被称为预言机（与 DBMS 无关），它们在复杂性理论中产生了有趣的结果。例如，贝克-吉尔-索洛维定理指出，存在预言机 A 和 B，对于可以访问 A 的图灵机，P=NP，但对于可以访问 B 的图灵机，P≠NP。 （A 是一个非常强大的预言机，它使得非决定论变得无关紧要；B 的定义有点复杂，并且涉及对角化技巧。）这是一种元结果：解决 P 与 NP 问题的任何证明都必须是敏感的足以满足图灵机的定义，当您添加某些类型的预言机时，它会失败。
非确定性图灵机的价值在于它们提供了复杂性类别 NP（和其他）的相对简单的计算特征：您可以想象一台几乎普通的计算机，而不是计算树或二阶逻辑公式被（相对）稍微修改，以便它可以做出完美的猜测。
A non-deterministic Turing machine is a tricky concept to grasp. Try some other viewpoints:
Instead of running a magical Turing machine that is the luckiest possible guesser, run an even more magical meta-machine that sets up an infinite number of randomly guessing independent Turing machines in parallel universes. Every possible sequence of guesses is made in some universe. If in at least one of the universes the machine halts and accepts the input, that's enough: the problem instance is accepted by the meta-machine that set up these parallel universes. If in all universes the machine rejects or fails to halt, the meta-machine rejects the instance.
Instead of any kind of guessing or branching, think of one person trying to convince another person that the instance should be accepted. The first person provides the set of choices to be made by the non-deterministic Turing machine, and the second person checks whether the machine accepts the input with those choices. If it does, the second person is convinced; if it does not, the first person has failed (which may be either because the instance cannot be accepted with any sequence of choices, or because the first person chose a poor sequence of choices).
Forget Turing machines. A problem is in NP if it can be described by a formula in existential second-order logic. That is, you take plain-vanilla propositional logic, allow any quantifiers over propositional variables, and allow tacking at the beginning existential quantifiers over sets, relations, and functions. For example, graph three-colorability can be described by a formula that starts with existential quantification over colors (sets of nodes):
Every node must be colored:
and no two adjacent nodes may have the same color – call the edge relation E:
The existential quantification over second-order variables is like a non-deterministic Turing machine making perfect guesses. If you want to convince someone that a formula ∃ X (...) is true, you can start by giving the value of X. That polynomial-time NTMs and these formulas not just "like" but actually equivalent is Fagin's theorem, which started the field of descriptive complexity: complexity classes characterized not by Turing machines but by classes of logical formulas.
You also said
Yes, you can. These are called oracle machines (no relation to the DBMS) and they have yielded interesting results in complexity theory. For example, the Baker–Gill–Solovay theorem states that there are oracles A and B such that for Turing machines that have access to A, P=NP, but for Turing machines that have access to B, P≠NP. (A is a very powerful oracle that makes non-determinism irrelevant; the definition of B is a bit complicated and involves a diagonalization trick.) This is a kind of a meta-result: any proof solving the P vs NP question must be sensitive enough to the definition of a Turing machine that it fails when you add some kinds of oracles.
The value of non-deterministic Turing machines is that they offer a comparatively simple, computational characterization of the complexity class NP (and others): instead of computation trees or second-order logical formulas, you can think of an almost-ordinary computer that has been (comparatively) slightly modified so that it can make perfect guesses.
你从中得到的好处是，你可以通过证明一个问题可以通过 NTM 在多项式时间内解决来证明它是 NP 问题。
换句话说，你可以使用 NTM 来确定给定问题是否属于 NP 问题。
What you gain from that is that you can prove that a problem is in NP by proving that it can be solved by an NTM in polynomial time.
In other words you can use NTMs to find out whether a given problem is in NP or not.
根据定义，NP 代表非确定性多项式时间，可以在 Wikipedia< 中查找/a>.
随机选择和检查（或组装）下一个潜在解决方案的非确定性图灵机的化身将以某种概率在多项式时间内解决 NP 问题（如果它是“最幸运的可能”，那么它将绝对确定地在多项式时间内解决该问题）猜测者”）。
因此，说 NTM 可以在多项式时间内有效解决问题意味着该问题属于 NP 问题。这又相当于 NP 类问题的定义。
By definition, NP stands for nondeterministic polynomial time as can be looked up in Wikipedia.
An incarnation of a nondeterministic Turing machine that randomly chooses and examines (or assembles) the next potential solution will solve an NP problem in polynomial time with some probability (it would solve the problem in poly time with absolute certainty if it were the "luckiest possible guesser").
Therefore, saying that an NTM can solve a problem in polynomial time effectively means that that problem is in NP. This again is equivalent to the definition of the NP class of problems.
我认为你的答案就在你的问题中。换句话说，给定一个问题，如果你能找到一个 NTM 来解决它，你就可以证明它是一个 NP 问题。
NP问题是一类特殊的问题，NTM只是检查给定问题是否属于该类的工具。
请注意，NTM 不是特定的机器 - 它是一整类机器，具有明确定义的规则，规定它们可以做什么和不能做什么。为了使用“神奇”的机器，您需要定义它们，并显示它们对应于哪一类复杂的问题。
请参阅http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes
了解更多信息。
I think your answer is in your question. In other words, given a problem you can prove that it is an NP problem if you can find an NTM that solves it.
NP problems are a special class of problems, and the NTM is just a tool to check if the given problem belongs to the class or not.
Note that the NTM is not a specific machine - it is a whole class of machines with well defined rules of what they can and cannot do. In order to use "magical" machines, you need to define them, and show which complexity class of problems they correspond to.
See http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes
for more info.
来自希伯来语维基百科 - “NTM 主要是一种思考工具，实际上不可能实现这样的机器”。您可以将术语“NTM”替换为“每一步都会尝试所有可能的步骤的算法”或“每一步都会选择最好的下一步的算法”。我认为您了解其余的内容。 NTM 在这里只是为了帮助我们可视化这种算法。您可以在此处查看 它应该如何帮助你可视化（在 Pascal Cuoq 的回答中）。
From Hebrew Wikipedia - "NTM is mainly a tool for thinking, and it's impossible to actualy implement such machine". You can replace the term "NTM" with "Algorithm that at every step tries all possible steps" or "Algorithm that at every step chooses the best possible next step".. And I think you understand the rest. NTM is here only to help us visualize such algorithm. You can see here how it's supposed to help you visualize (at Pascal Cuoq's answer).
我们得到的是，如果我们有能力猜测正确的步骤，并且结果总是正确的，我们就可以在 POLYTIME 中解决 NPC 问题。当然，我们不能总是“猜测”正确的步骤。所以这是想象的。但正如虚数适用于现实世界的问题一样，结果在理论上也是有用的。
以这种方式改变原始问题的一个积极方面是我们可以从不同的角度解决它们。在理论领域，这是一件好事，因为我们有（1）更多可以采取的方法（因此有更多论文）和（2）我们可以使用更多工具（如果它们可以在其他领域使用）。
What we gain is that if we have the magical power to guess the correct step, which will always turn out to be correct, we can solve NPC problems in POLYTIME. Of course, we can't always "guess" the correct step. So it's imaginary. But just as imaginary numbers are applicable to real world problems, consequences can be theoretically useful.
One positive aspect of morphing the original problems this way is that we can tackle them from different angles. In a theoretical domain, it is a good thing because we have (1) more approaches we can take (thus more papers) and (2) more tools we can use if they can be phrased in other fields.