既然所有可用的问题都已经被分类，而且它们的时间复杂性也被推断出来了，那么为什么还没有人解决NP对P呢？

Question

我们在P，NP，co，NP-完全类和NP-Hard类中证明了一些问题.这些问题也有其时间复杂性的推论。我想知道我是否遗漏了关于这个主题的任何关键信息。

Answer 1

解决这类问题的标准技巧之一是使用“甲骨文”。假设我们可以问甲骨文一个关于某一类问题的问题，在一个步骤中，它会回答“是”或“否”。它变得合理地问，“在P是什么类型的问题，一个机器与此神谕”？“对于带有此Oracle的机器来说，NP中存在什么样的问题。

已经证明，有一些先知，P=NP。结果表明，P≠NP具有预言性。我们所知道的大多数检验硬度的方法都应该给出相同的结果，不。不管神谕是怎么用的。