什么是班级的图灵机器

Question

关于Wikipedia关于多项式层次结构的文章 http://en.wikipedia.org/wiki/polynomial_hierarchy

它说：“ $ a^b $是Turing机器在A类中可解决的一组决策问题。

P，NP和Conp类的“ A级Turing Machine”是什么？

我猜P中的图灵机是一台确定性的图灵机，只能在其输入大小的多项式时间内运行

NP中的图灵机是一台非确定的图灵机，只能在其输入大小的多项式时间内运行

但是我不知道班级的图灵机是什么？

Answer 1

你 能够 将Co-np定义为：$$ {l mid envists text {polyn.time} text {ntm} m：l = {w mid mid text {} m（w）的所有计算路径{Accept} } } $$这直接对应于上述文章的下一节中的$ forall^p $ operator的定义。但是，NP的几乎所有定义都依赖于TMS或通常可以配备甲壳的其他算法概念。

但是，您已经很好地发现了复杂性类别的Oracle定义问题：$ Mathcal A^{ Mathcal B} $隐含地假设可以使用Turing Machines来定义$ Mathcal a $，而可能是任何一组语言。有时，通过将$ Mathcal a $定义为一组图灵机或算法来避免这种情况（通常用与这些算法定义的复杂性类相同的名称表示）。

Answer 2

最简单的方法（对我来说）理解Co-NP是一类问题，可以快速验证“无”答案的证书（即非会员证书）。

因此，如果我们将NP视为一类非确定的Turing机器，这些机器很快（在多项式时间）确定他们的输入满足某些属性$ pi $，则Co-NP是一类非确定的Turing机器，这些机器很快确定其输入并不确定他们的输入不在满足$ pi $（或等效地满足$ neg pi $）。