我正在尝试理解这些语言类别之间的关系。 有人可以按照我的想法做一些排序吗？例如，如果我使用语言 HAMPATH = {: G has a hamiltonion path}。我知道这是 NP 和 NP hard。这是否教会了我关于在 R, RE core 中的任何事情？它们之间有什么联系吗？
最佳答案
P、NP 和 co-NP 中的所有问题都是可判定的，因此所有这些类都是 的严格子集R。众所周知，R 是 RE 和 co-RE 的严格子集，此外，R = RE∩共同RE。
这些类之间有很好的直观联系。 R、RE 和 co-RE 的定义本质上可以描述为
- R 语言是可以决定的语言。
- RE 语言是具有验证器的语言。
- co-RE 语言是其补语在RE 中的语言。
P、NP和co-NP的定义是
- P 语言是可以在多项式时间内决定的语言。
- NP 语言是具有验证器的语言在多项式时间内运行。
- co-NP 语言是其补语在NP 中的语言。
从某种意义上说，您可以通过添加或删除多项式时间限制从一类语言转到另一类语言。 (这也有助于解释收容措施)。
关于turing-machines - 相对于 P、NP、coNP，类 R、RE coRE 之间的关系是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38356305/