2

我刚开始学习复杂性理论。我从过去的四五天开始寻找，只有一件事。是否有任何问题存在于 NP 而不是 NPC 和 NPH。看这个图（认为 P 不等于 NP）。

考虑 P in 不等于 NP

P外面有空间，不是NPC的一部分。我想知道，是否存在任何问题？

4

2 回答 2

2

要回答这样的问题，记住 P = NP 和 P != NP 的含义很有用。

  • 如果 P=NP，(P = NP = NPC) 是 NPH 的子集
  • 如果 P!=NP, (P != NP != NPC) 并且只有 NPC 是 NPH 的子集
  • 在任何一种情况下，P 和 NPC 都是 NP 的子集

综上所述，如果 NP 中有一个问题被证明不存在于 NPC 中，则将排除 P=NP 的可能性，证明 P!=NP。

因此，是否存在这样的问题，我们目前不知道。

于 2018-04-12T13:23:05.107 回答
1

所以，首先要重申这个问题：是否存在一个存在于 NP 中但既不在 P 中，也不在 NPC 或 NPH 中的问题？

让我们从 NP 完全类的定义开始：一个问题p是 NP 完全的，如果它本身是 NP 并且每个NP问题q都可以多项式简化为p。

接下来，NP-hard 类的定义：h如果存在一个p可以多项式简化为 的 NP-完全问题，则该问题是 NP-hard h。

这两个定义是什么意思：

  • NP 完全问题形成了 NP 的一个子集，该子集具有每个 NP 问题都可以多项式地简化为任何一个问题的性质，包括它们自己。
  • NP难问题不需要是NP完全的。通过多项式归约，您可以使问题“更难”，但不能“更容易”。
  • 根据 NP-hard 的定义，所有 NP 问题都可以归约为 NP-hard 问题。
  • 因此，NP-hard 问题要么是 NP 完全的，要么根本不是 NP。

现在回到问题 - 是否存在 NP 但既不是 P、也不是 NP 完全、也不是 NP 难的问题？

首先，问题必须是NP。从 NP 类的定义来看，这很容易。它是可以多项式验证其解决方案的一组问题。这立即意味着这样的问题不会是 NP 难的。

其次，问题一定不是 P。这不能说是因为我们不知道 P = NP 但我们假设 P != NP 所以我们可以因此假设实际上可能存在一个问题是 NP 但不是P。

最后，我们需要证明这个问题不是NP 完全的。从定义上看，NP 完全问题具有每个NP 问题都可以归约到它的性质（更正式地说，对于每个 NP 问题都有一个多项式归约......）。因此，对此的否定是，至少有一个NP 问题不可归约（更正式地说，没有多项式归约……）。但在我看来，证明没有减少是不可能的。

所以，最后，这是关于我们（你的）证明此类问题的 NP 完全性的能力。如果是，您可以证明一个问题是 NP 完全的，但在我看来，证明相反的问题是不可能的。

我欢迎所有受过理论教育的人来编辑我的答案以使其更准确。

于 2016-05-26T12:11:55.920 回答