21

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

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

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

一种。找到一个不确定的算法来解决它（使用选择、成功、失败）；

湾。将一个已知的 NP 完全问题简化为它。

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

我的问题是——我从来没有遇到过在多项式时间内和指数时间内都无法解决的问题；多项式时间问题属于 P，而指数时间问题通常属于 NP 完全问题。

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

  1. 我想知道一个问题的例子，它既不在 P 中，也不在 NP-complete 中，但在 NP 中。

  2. 此外，本质上是指数问题，例如生成一组 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 如果与最初的问题不完全相关，这通常很有趣。

非常感谢，

担

4

4 回答 4

13

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

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

于 2010-12-13T14:31:31.507 回答
8
  1. BQP 问题，例如整数分解和离散对数（破解 RSA 和 DSA）被认为是 P 之外的问题，也被怀疑是 NP 问题，但不是 NP 完全问题。整数分解已知在 NP 中，并且应该在 P 和 NP 完全之外。

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

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

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

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

于 2010-12-13T14:23:51.740 回答
3

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

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

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

于 2010-12-13T14:36:09.713 回答
1

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

可能有帮助。

于 2010-12-13T14:16:50.213 回答