说不确定的图灵机可以在多项式时间内求解NP有什​​么后果？ [英] What are the consequences of saying a non-deterministic Turing Machine can solve NP in polynomial time?

问题描述

这些天，我一直在研究NP问题，计算复杂性和理论。我相信我终于掌握了Turing Machine的概念，但我有一些疑问。为读取给定的状态和符号做准备，并且它将始终选择最佳选择，如Wikipedia所述

NTM如何知道应该采取哪些
动作？有两种
的查看方式。一个是说
这台机器是最幸运的
猜测者；它总是选择
过渡，如果有这样的
过渡，最终会导致
成为接受状态。另一个是想像
，该机器分支成许多
副本，每个副本遵循
可能的转换之一。
DTM具有遵循的单个计算路径
，而NTM具有
计算树。如果树中
的任何分支因接受
条件而停止，我们说NTM接受
的输入。

我不明白的是，由于这是一台虚构的机器，因此说它可以在多项式时间内解决NP问题有什么好处？我的意思是，我也可以将解决O（1）中的NP问题的神奇机器理论化，如果它可能永远不存在，我将从中得到什么？

解决方案

不确定的图灵机是一个棘手的概念。尝试其他一些观点：

1. 而不是运行可能是最幸运的猜测者的神奇图灵机，而是运行更神奇的元数据-在平行宇宙中设置无限数量的随机猜测独立图灵机的机器。每一个可能的猜测序列都是在某个宇宙中做出的。如果机器在至少一个Universe中停止并接受输入，那就足够了：问题实例被设置这些并行Universe的元计算机接受。如果在所有宇宙中机器拒绝或无法停止，则元机器拒绝该实例。




2. 而不是任何类型的猜测或分支，而想到一个试图说服另一个人该实例应被接受的人。第一人称将提供由不确定性图灵机做出的选择集，第二人称将检查机器是否接受带有这些选择的输入。如果是这样，第二个人就被说服了。如果不是，则第一人称失败（这可能是因为该实例无法接受任何选择序列，或者是因为第一人选择了一个错误的选择序列）。




3. 忘记图灵机。如果可以用存在的二阶逻辑中的公式来描述，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和这些公式不仅像，而且实际上等效于Fagin定理，该定理开始于描述性复杂度：不是由图灵机而是由逻辑公式组成的复杂度类。

您还说过

我也可以对一台神奇的机器进行理论化可以解决O（1）中的NP问题

是的，您可以。这些被称为 oracle机器（与DBMS没有关系），并且它们在复杂性理论上产生了有趣的结果。 。例如，贝克·吉尔·索洛维定理指出存在预言A和B，使得对于图灵机可以访问A，P = NP，但对于图灵机可以访问B，P≠ NP。 （A是一个非常强大的预言家，它使不确定性无关紧要； B的定义有点复杂，并且涉及对角线化技巧。）这是一种元结果：解决P vs NP问题的任何证明都必须敏感足以说明图灵机的定义，当您添加某种预言机时，该图灵机将失败。

---

确定性图灵机是它们为复杂度等级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.

解决方案

A non-deterministic Turing machine is a tricky concept to grasp. Try some other viewpoints:

1. 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.

2. 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).

3. 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):

   ∃ R ∃ G ∃ B

   Every node must be colored:

   ∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x)))

   and no two adjacent nodes may have the same color – call the edge relation 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)))))

   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

I could also theorize of a magical machine that solves NP problems in O(1)

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.

这篇关于说不确定的图灵机可以在多项式时间内求解NP有什​​么后果？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！