computer-science - 示例问题不是P也不是NP完全的，而是NP中的问题

Question

我在大学里有一门名为算法分析的类(class)，我们目前正在研究不同的复杂度类别-P，NP，NP-hard等。

我们已经讨论了NP-完全问题，即NP和NP-hard之间的交集，以及NP中包含的P问题。我们还讨论了一些示例，主要是NP完全问题(k着色，k clique，SAT)。

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

一种。寻找一种不确定的算法来解决(使用选择，成功，失败)；

b。减少一个已知的NP完全问题。

问题是，当这些问题在确定性机器上运行时(顺序地，而不是在遇到选择时同时分支)，它们具有指数时间解。

我的问题是-我从未遇到过在多项式时间和指数时间都无法解决的问题；多项式时间问题在P中，而指数时间问题通常在NP-完全中。

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

我想知道这个问题的例子，它既不在P中，也不在NP-complete中，而在NP 中。

另外，是否存在内在的指数问题，例如生成NP完全集的幂集？ 还是该名称仅适用于仅由于没有其他明显的解决方法而使用指数时间算法的问题？

好的，所以我给Rosh Oxymoron回答，因为他实际上列出了一些疑似在P和NPC之间的问题的示例。感谢您的帮助，我实际上注意到我将这个问题放在错误的位置。
还有:
https://cstheory.stackexchange.com/

在这里，我找到了以下非常有用的答案:
https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc
具体是关于我的要求，以及:
https://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np
即使与最初的问题不完全相关，这通常也很有趣。

非常感谢，

担

Answer 1

BQP问题(例如整数分解和离散对数(破解RSA和DSA))被认为不在P范围内，并且也被怀疑存在于NP中，而不是在NP-complete中。整数分解已知在NP中，并且应该在P和NP完全之外。

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

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

NP是EXPTIME的子集，但可以预期NP!= EXPTIME(即，NP中不存在EXPTIME-complete问题)。像P = NP一样，这尚未得到证明(但已知P!= EXPTIME)。例如，检查算法是否将在k个步骤后将完成一半是EXPTIME-complete。寻找功率设定也是(显然)。

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