Cla*_*ash 9 theory complexity-theory turing-machines
这些天我一直在研究NP问题,计算复杂性和理论.我相信我终于掌握了图灵机的概念,但我有一些疑惑.
我可以接受一个非确定性的图灵机有几个选项,可以为给定的状态和符号读取做什么,它总是会选择最佳选项,如维基百科所述
NTM如何"知道"它应该采取哪些行动？有两种方式可以看待它.一个是说机器是"最幸运的猜测者"; 如果存在这样的转变,它总会选择最终导致接受状态的过渡.另一种是想象机器"分支"成许多副本,每个副本都遵循一个可能的过渡.虽然DTM具有它遵循的单个"计算路径",但NTM具有"计算树".如果树的任何分支以"接受"条件停止,我们说NTM接受输入.
我无法理解的是,既然这是一个虚构的机器,我们从多数时间内解决NP问题得到什么呢？我的意思是,我还可以理解一个解决O(1)中NP问题的神奇机器,如果它可能永远不会存在,我会从中获得什么？
提前致谢.
Jou*_*nen 14
非确定性图灵机是一个难以理解的概念.尝试其他一些观点:
而不是运行一个神奇的图灵机,这是最幸运的猜测器,运行一个更神奇的元机器,在平行的宇宙中建立无限数量的随机猜测独立的图灵机.每个可能的猜测序列都是在某个宇宙中进行的.如果在至少一个Universe中机器停止并接受输入,那就足够了:设置这些并行Universe的元机器接受问题实例.如果在所有Universe中机器拒绝或未能停止,则元机器拒绝该实例.
想象一个人试图说服另一个人该实例应该被接受,而不是任何猜测或分支.第一人提供由非确定性图灵机做出的一组选择,第二人检查机器是否接受具有这些选择的输入.如果确实如此,那么第二个人就会相信; 如果没有,则第一个人失败(这可能是因为实例不能被任何选择序列接受,或者因为第一个人选择了不良的选择序列).
忘记图灵机.如果可以通过存在性二阶逻辑中的公式来描述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的值.那个多项式时间NTMs和这些公式不仅仅是"喜欢"而且实际上是等价的是Fagin定理,开始描述复杂性的领域:复杂性类不是由图灵机而是由逻辑公式的类来表征.
你也说过
我还可以理论化一台解决O(1)中NP问题的神奇机器
是的你可以.这些被称为oracle机器(与DBMS无关),它们在复杂性理论中产生了有趣的结果.例如,Baker-Gill-Solovay定理表明存在神谕A和B,使得对于可以访问A的Puring机器,P = NP,但是对于可以访问B的图灵机,P≠NP.(A是一个非常强大的oracle,它使非决定论无关紧要; B的定义有点复杂并且涉及对角化技巧.)这是一种元结果:任何解决P vs NP问题的证据必须是敏感的足以定义图灵机,当你添加某些类型的神谕时它会失败.
非确定性图灵机的价值在于它们提供了复杂性类NP(和其他)的相对简单的计算表征:代替计算树或二阶逻辑公式,你可以想到一台几乎普通的计算机(相对)略微修改,以便它可以做出完美的猜测.