示例问题不在P中,也不在NP完全中,而是在NP中

Question

我在大学里有一门名为算法分析的课程,我们目前正在研究不同的复杂性类别 - P,NP,NP-hard等.

我们已经讨论过NP完全问题作为NP与NP之间的交集,以及NP中包含的P问题.我们还讨论了一些例子,主要是NP完全问题(k-coloring,k-clique,SAT).

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

一个.找到一个不确定的算法来解决它(使用选择,成功,失败);

湾 减少已知的NP完全问题.

问题是这些问题,当在确定性机器上运行时(顺序而不是在遇到选择时同时分支)具有指数时间解决方案.

我的问题是 - 我从未遇到过在指数时间内既不能在多项式时间内解决的问题; 多项式时间问题在P中,指数时间问题通常在NP完全中.

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

1. 我想知道一个问题的例子既不是在NP中,也不是在NP中.

2. 另外,本质上是指数问题,比如生成NP-complete集的幂集？或者该名称仅适用于仅使用指数时间算法的问题,因为没有其他明显的方法可以解决它？

好的,所以我给了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/hierarchyies-in-np-under-the-assumption-that-p-np ,如果与初始问题不完全相关,通常很有趣.

非常感谢,

担

Answer 1

我想知道一个问题的例子既不是在NP中,也不是在NP中.

我也是; 如果你找到一个,请访问这个网页,以获得你的100万美元奖金:http: //www.claymath.org/millennium/P_vs_NP/

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