一个问题可以在NP中而不是NP-Complete或P中吗？

Question

我正在查看中的图表：https://en.wikipedia.org/wiki/P_versus_NP_problem

似乎，在P和NP-完全之间存在差距。那么是否有一类问题在NP中，但既不在P中，也不在NP-完全中。

换句话说，类P，NP-complete是否完全覆盖NP？

如果是这样的话，请举个例子。

Answer 1

如果P= NP，则您的问题的答案是NP中的所有问题都是P中的问题和NP-完全中的问题。

如果P != NP，则您的问题的答案是存在已知的NP中的问题，这些问题不是NP完全的，但尚不知道其多项式时间算法。我说还没有，因为如果你知道(1)问题在NP中，(2)问题不在P中，那么你就会知道P != NP，而我们不知道。