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

Question

我试图了解这些语言类别之间的关系。有人可以按照我的想法排序吗？例如，如果我采用语言 HAMPATH = {: G has a hamiltonion path}。我知道这是 NP 和 NP 难。这是否教会了我关于 R、RE 核心的任何信息？它们之间有什么联系吗？

Answer 1

P、NP和 co- NP中的所有问题都是可判定的，因此所有这些类都是R 的严格子集。众所周知，R是RE和 co- RE的严格子集，此外，R = RE ∩ co- RE。

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

• R语言是可以决定的语言。
• RE语言是具有验证器的语言。
• co- RE语言是补语在RE中的语言。

P、NP和 co- NP的定义是

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

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