NP和NP-HARD之外是否存在任何决策问题?
题
这个问题 询问NP不完整的NP硬性问题。我想知道是否存在任何不属于NP的决策问题 也不 np-hard。
为了进入NP,问题必须具有确定性图灵机上多项式时间运行的验证者。显然,P中的所有问题都符合该标准,但是亚指数复杂性的问题又如何呢?他们不属于P,对我来说并不明显,他们都有有效的决策者。而且他们当然没有资格参加NP完整。
我愿意相信所有决策问题都是NP或NP-HARD或两者兼而有之,但实际上没有人 说 那(我可以找到)。我也愿意相信这些问题确实存在,即使它们是非常人为的。也许有更多知识渊博的人可以将这个问题归结为我。谢谢。
编辑
我在问题中滥用了“副指数”一词。在我看来,这意味着有些问题,在指数和多项式(如l)之间存在复杂性。 这个表. 。有关更多详细信息,请参见拉斐尔答案中的链接。
不隶属于 cs.stackexchange