time-complexity - 既然已经对所有可用的问题进行了分类并推断了它们的时间复杂度，那么为什么还没有人解决 NP 与 P 的问题呢？

Question

我们有问题被证明属于 P、NP、co-NP、NP-Complete 和 NP-Hard 类。这些问题也推导出了它们的时间复杂度。我想知道我是否遗漏了有关该主题的任何关键信息。

Answer 1

解决这类问题的标准技巧之一就是所谓的使用“预言机”。假设我们可以向 oracle 询问有关特定类别问题的问题，并且在一个步骤中它会回答“是”或“否”。有理由问“对于具有此预言机的机器，P 中存在哪些类型的问题”？“使用这个 Oracle 的机器在 NP 中存在什么样的问题。

已经证明存在 P=NP 的预言机。已经证明存在 P≠NP 的预言机。我们知道的大多数证明硬度的技术应该给出相同的结果，不。不管使用什么预言机。