类 R、RE coRE 与 P、NP、coNP 之间的关系是什么

Question

我试图理解这些 类 语言之间的关系。 有人可以按照我的想法做一些排序吗？例如，如果我使用语言 HAMPATH = {: G has a hamiltonion path}。我知道这是 NP 和 NP hard。这是否教会了我关于在 R, RE core 中的任何事情？它们之间有什么联系吗？

Answer 1

P、NP和co-NP中的所有问题都是可判定的，所以所有这些 classes 都是 R 的严格子集。众所周知 R 是 RE 和 co-RE 的严格子集，而且， R = RE ∩ co-RE.

这些 class 之间有很好的直观联系。 R、RE、co-RE的定义本质上可以描述为

• R语言是可以决定的语言。
• RE 语言是具有验证器的语言。
• co-[​​=20=]RE 语言是补语在 RE.
中的语言

P、NP、co-NP的定义是

• P语言是可以在多项式时间内决定的语言.
• NP 语言是具有验证器 在多项式时间内 运行 .
的语言
• co-[​​=20=]NP 语言是补语在 NP.
中的语言

从某种意义上说，您可以通过添加或删除多项式时间限制从一种 class 语言切换到另一种语言。 （这也有助于解释收容措施）。