33

我不了解非确定性图灵机的概念。我想我理解术语非确定性算法：（非确定性算法是一种算法，它可以在不同的运行中表现出不同的行为，而不是确定性算法。）所以算法可能像：

a = fromSomeAlgo();

if(a > foo)
   stateA();
else
   stateB();

但是对于我读过的非确定性图灵机，它在给定时间可以处于多个状态。还有一篇维基百科文章建议“非确定性图灵机 (NTM)，可能有一组规则，为给定情况规定了多个动作”。

这意味着什么 ？..针对给定情况的不止一个动作...多个状态...我根本不明白这一点。

4

1 回答 1

47

在非确定性图灵机中，在每个分支中——你都做了两种可能性——只有当你完成后，你才“选择”哪一个是你需要的解决方案（如果存在的话）。

例如，让我们看一下子集和问题，其中S = {a,b,c... }. 非确定性图灵机有一个线性解：

for each element:
   "guess" if it is in the subset
check if the subset has the specified sum

生成的树将是这样的：

                                       start
                 with a                                      without a
               /         \                                   /          \
              /           \                                 /            \
             /             \                               /              \
      with b               without b                  with b              without b
      /     \               /       \                 /     \             /        \
  with c    without c    with c     without c     with c    without c    with c     without c

一个计算（树中的路径）是正确的就足够了，以便算法产生“真”。只有在没有这样的计算时才会产生“假”。

非确定性图灵机的概念纯粹是理论上的——没有可用的非确定性图灵机。

奖励：
请注意，可以使用非确定性图灵机完成的所有事情 - 都可以使用确定性图灵机完成（反之亦然） - 例如，停机问题在任何一个中都无法决定。但是，NPC 问题可以在非确定性图灵机中以多项式方式完成，我们不知道（并且我们假设我们不能）如何在确定性图灵机上以多项式方式完成。

于 2012-11-23T06:53:30.687 回答