一个“自然”可决定的问题，不在$ mathsf {np} $中？ [复制

Question

这个问题在这里已经有一个答案：

• NP不在NP中但可决定的NP难题 2个答案

是否有任何“自然”的示例，这些示例明确地知道不在 NP？我知道的可决定性语言不包含在 NP 通常源自时间层次定理，该定理产生基于对角化的“人造”语言。

Answer 1

从答案到 相关问题 NP- 不包含的问题 NP: ：可能最自然的例子是确定两个正则表达式（包括用于任意重复的Kleene Star和平方操作以允许非常固定数量的重复数量的紧凑表达式）是否等效。结果问题是 expspace 完全的。因为 expspace 包含 nexp, ， 其中包含 NP 严格（到层次定理时），这是一个可决定的问题，不在 NP.

Answer 2

一个变体 发布对应问题 对于有限的长度输入（但是 不是 Garey/Johnson中的标准“有限”版本称为“有限的PCP”，该版本限制了解决方案中的块中块的块数量）对于Nexpspace而言是完整的，因此在PSPACE中正确的NP大于NP。 [1

即，让二进制中指定的输入参数$ n $确定PCP答案的最大长度。这显然是通过StraightFWD证明Nexpspace完成的。尚未在文献中看到证据。它以类似于[2]中TMS的构建方式进行的方式进行。

请注意，所有已知大于NP的问题也大于PSPACE。否则它（一种不在NP中但仍在PSPACE中的语言的证明）可能接近conp $ neq $ np，因此也是p $ neq $ np证明（因为p在补充下关闭），或解决当前开放的复杂性类别分离的其他一些“附近”。

[1] 邮政通讯问题的可决定限制

[2] 从任何NP完整问题降低到有限的PCP的多项式减少