我不明白非确定性图灵机的概念

Question

我不理解非确定性图灵机的概念.我想我理解术语非确定性算法 :(非确定性算法是一种算法,可以在不同的运行中表现出不同的行为,而不是确定性算法.)所以算法可能是这样的:

a = fromSomeAlgo();

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

但是对于我读过的非确定性图灵机,它可以在给定时间处于多个状态.另外一篇维基百科文章暗示"非确定性图灵机(NTM),可能有一套规则,规定了针对特定情况的多个动作".

那是什么意思 ？..对于给定的情况,不止一个行动......多个州......我根本就不明白这一点.

Answer 1

在非确定性图灵机中,在每个分支中 - 您都有两种可能性 - 只有当您完成后,您才"选择"哪一个是解决方案所需的那个(如果存在).

例如,让我们来看看子集和问题,有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问题可以在非确定性图灵机中以多项式进行,我们不知道(并且我们假设我们不能)如何在确定性图灵机上进行多项式处理.