示例问题不在 P 中，也不在 NP 完全中，但在 NP 中

Question

我在大学有一门叫做算法分析的课程，我们目前正在研究不同的复杂性类别——P、NP、NP-hard 等。

我们已经讨论了 NP 完全问题作为 NP 和 NP-hard 之间的交集，和P问题，包含在NP中。我们还讨论了一些示例，主要是 NP 完全问题（k-coloring、k-clique、SAT）。

大多数时候，我们通过以下方式证明问题是 NP 完全的

：找到一个非确定性算法来解决它（使用选择、成功、失败）；

b.将已知的 NP 完全问题简化为它。

问题是，这些问题在确定性机器上运行时（顺序地，而不是遇到选择时同时分支）具有指数时间解决方案。

我的问题是这样的——我从来没有遇到过既不能在多项式时间内解决也不能在指数时间内解决的问题；多项式时间问题是 P 型问题，而指数时间问题通常是 NP 完全型问题。

这里有一个有用的维恩图： http://en.wikipedia.org/wiki/Np_complete

1. 我愿意知道一个问题的例子，该问题既不在P中，也不在NP完全中，而是在NP中。

2. 此外，本质上是指数问题，例如生成 NP 完全集的幂集吗？或者该名称仅适用于仅使用指数时间算法的问题，因为没有其他算法显然的解决方法？

好吧，所以我给了 Rosh Oxymoron 答案，因为他实际上列出了一些疑似 P 和 NPC 之间问题的例子。感谢你们的帮助，我实际上注意到我把这个问题放在了错误的地方。 还有： https://cstheory.stackexchange.com/

我在其中找到了以下对我的问题非常有用的答案： https://cstheory.stackexchange.com/questions/79/problems- Between-p-和-npc 这具体是关于我问的问题，并且： https://cstheory.stackexchange.com/questions/ 52/hierarchies-in-np-under-the-p-np假设下 这通常很有趣，即使与最初的问题不完全相关。

非常感谢，

丹

Answer 1

我想知道一个既不是 P 问题，也不是 NP 完全问题，而是 NP 问题的例子。

我也是;如果您找到了，请访问此网页领取 100 万美元奖金：https://www.claymath.org/millennium-problems/p-vs-np-problem

Answer 2

1. BQP 问题，例如整数分解和离散对数（破解 RSA 和 DSA），被认为是 P 之外的，也被怀疑是 NP 问题，但不是 NP 完全问题。已知整数分解是在 NP 中，并且应该在 P 和 NP 完全之外。

http://en.wikipedia.org/wiki/BQP

http://en.wikipedia.org/wiki/Integer_factorization

2. NP 是 EXPTIME 的子集，但预计 NP != EXPTIME （也就是说，EXPTIME 完全问题不在 NP 中）。与 P = NP 一样，这尚未得到证明（但已知 P != EXPTIME）。例如，检查算法是否会在 k 步后减半是 EXPTIME 完成的。寻找幂集也是如此（显然）。

http://en.wikipedia.org/wiki/EXPTIME

Answer 3

1. NP \ NPC 中没有已知的问题。

2. 当且仅当非确定性图灵机可以在多项式时间内解决该问题（或者等效地，确定性图灵机可以在多项式时间内决定该问题）时，该问题才是 NP 问题。您的示例并非如此。

   进一步需要指出的是，我们不知道 P = NP 是否存在，因此完全有可能（如果可能性很小）NP 中的所有问题都可以解决在多项式时间内。因此，如果我们知道一个问题无法在多项式时间内解决，那么该问题要么不是 NP 问题，要么，如果我们可以证明它确实是 NP 问题，我们只需证明 NP != P .

Answer 4

袁翘楚，有哪些技术可以证明问题不是 NP 完全的？，

可能会有所帮助。