示例问题不属于P类问题也不属于NP完全问题，但属于NP问题。

Question

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

我们已经讨论了NP完全问题作为NP和NP-hard交集，并且包含在NP中的P问题。我们也谈到了一些例子，主要是NP完全问题（k着色、k团、SAT）。

大部分时间，我们通过以下方式证明一个问题是NP完全的：

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

b. 将一个已知的NP完全问题归约到它上面。

问题在于，当在确定性机器上运行这些问题时（顺序地运行，而不是在遇到选择时同时进行分支），其解决方法具有指数级的时间复杂度。

我的问题是这样的——我从未遇到过既可在多项式时间内解决又可在指数时间内解决的问题；多项式时间问题属于P，指数时间问题通常属于NP完全。

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

1. 我想知道一个既不属于P，也不属于NP完全，但属于NP的问题的例子。

2. 此外，类似于生成一个集合的幂集是否是NP完全问题的内在指数问题？或者这个名字只适用于那些仅因为没有其他明显的解决方法而使用指数时间算法的问题？

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

在那里我找到了对我的问题非常有用的答案：

这个链接专门讨论了我提出的问题，内容涉及IT技术；这个链接则是非常有趣的内容，虽然与最初的问题不完全相关。

非常感谢，

Dan

- Dan Filimon

---

请参考[cs.SE]上的这个和这个问题。 - Raphael

Answer 1

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

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

- Kevin L. Stern

---

@iamrohitbanga 要将BQP用作P≠NP证明，必须证明所有这些事情：1. BQP ⊆ NP 2. P ⊊ BQP 3. BQP ∩ NPC = ∅。目前所有这些都未知。 - dtech

Answer 2

1. 被认为不属于P类问题，且被怀疑不属于NP-complete类别的BQP问题包括整数分解和离散对数（破解RSA和DSA）。整数分解已知属于NP类别，且被认为不属于P类别和NP-complete类别。

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

- Rosh Oxymoron

---

强调一下，第一点是猜想。如果P=NP，则不存在这样的问题，但如果P！=NP，则我们知道 NPI不为空。 - Raphael

Answer 3

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

2. 如果一个非确定性图灵机可以在多项式时间内解决问题（或者等效地，确定性图灵机可以在多项式时间内判断问题），那么该问题就属于NP。但你提到的问题并不属于这种情况。

   此外，需要指出的是我们不知道P = NP，因此所有NP问题都能在多项式时间内解决是完全有可能的（尽管高度不太可能）。因此，如果我们知道一个问题不能在多项式时间内解决，那么这个问题要么不属于NP，要么，如果我们能证明它确实属于NP，那么我们就证明了NP != P。

- sepp2k

---

1. 我认为P≠NP是有争议的，对吗？
2. 啊，我明白你的观点了，非确定性机器仍然无法找到那个问题的答案。那么，它真正属于哪个类别呢？

- Dan Filimon

@Dan：1. 是的，人们相信 P != NP，这就是我说 P = NP 被认为是错误的原因。然而，由于我们不知道它是否为假，我们也不知道任何 NP \ NPC 中的问题（尽管我们可能怀疑它们存在）。2. 它在 EXPTIME 中。 - sepp2k

哦，我一开始误解了 - 我没有注意到括号中整个句子。 - Dan Filimon

@sepp2k 关于1：通常即使P=NP，也不会将所有NP问题视为NP完全问题，因为你并不总是要将它们归约到这些问题上。例如，以∅为例，无法将任何具有yes实例的语言归约到它，但它属于P（算法：“返回FALSE”）。 - dtech

（或等价地，确定性图灵机可以在多项式时间内决定它）- 这并不等价。然而存在一个可以验证解决方案的确定性图灵机。 - Kent Munthe Caspersen

Answer 4

Qiaochu Yuan, 有哪些技巧可以证明一个问题不是NP完全的？,

可能会有所帮助。

- Itay Karo