Может ли проблема быть в NP, но не в NP-Complete или P?

Question

Я смотрю на графики в: https://en.wikipedia.org/wiki/P_versus_NP_problem

Кажется, что есть разрыв между P и NP-complete. Так есть ли класс задач, которые есть в NP, но не в P или NP-Complete.

Другими словами, полностью ли классы P, NP-complete покрывают NP?

И если Итак, пример приветствуется.

Answer 1

Если P = NP, ответ на ваш вопрос заключается в том, что все проблемы в NP находятся как в P, так и в NP-Complete.

Если P! = NP, ответ на ваш вопрос заключается в том, что есть проблемы, о которых известно, что они есть в NP, которые, как известно, не являются NP-полными, но для которых еще не известен алгоритм полиномиального времени. Я говорю, что еще ничего не известно, потому что если бы вы знали (1) проблема в NP, и (2) проблема не в P, то вы бы знали P! = NP, а мы нет.