这个问题 询问NP不完整的NP硬性问题。我想知道是否存在任何不属于NP的决策问题 也不 np-hard。

为了进入NP,问题必须具有确定性图灵机上多项式时间运行的验证者。显然,P中的所有问题都符合该标准,但是亚指数复杂性的问题又如何呢?他们不属于P,对我来说并不明显,他们都有有效的决策者。而且他们当然没有资格参加NP完整。

我愿意相信所有决策问题都是NP或NP-HARD或两者兼而有之,但实际上没有人 那(我可以找到)。我也愿意相信这些问题确实存在,即使它们是非常人为的。也许有更多知识渊博的人可以将这个问题归结为我。谢谢。

编辑

我在问题中滥用了“副指数”一词。在我看来,这意味着有些问题,在指数和多项式(如l)之间存在复杂性。 这个表. 。有关更多详细信息,请参见拉斐尔答案中的链接。

有帮助吗?

解决方案

NP包含所有(决策)问题 最多 与NP完整问题有关 减少KARP.

NP-HARD包含所有(决策)问题 至少 与NP完整问题有关 减少KARP.

因此,在“减少KARP减少宇宙”中,NP和NP-Hard确实涵盖了一切。但是,可能有正交问题类:例如, Co-NP如果NP不等于Co-NP,则既不在NP也不是NP-HARD(WRT KARP减少)(我们不知道)。

除此之外,请注意 那里 NP完整问题的亚指数算法, ,但没有已知的多项式。

谢谢 Frafl 指出此答案的初始版本中的关键缺陷。旧版本的读者可能想要阅读 这个.

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top