每种语言都属于P语言还是NP语言？

Question

为什么我要读一本关于迈克尔·西普瑟的计算理论的书，我有一个小问题:是每种语言都属于P还是NP？

Answer 1

不，不是所有的语言都用P或NP。这里有几种方法可以看到这一点：

1. 在P和NP中有无数的语言，但只有可数的多种语言。这意味着，特别是，如果你随机选择一种语言，概率1，你选择一种语言而不是P或NP。
2. P和NP的所有语言都是可分辨的。任何不可分辨的语言，如停止问题，都不能用NP。
3. 非确定性时间层次定理可以用来说明在NEXP中有一些语言不是NP语言。

希望这能有所帮助！