Примеры задач не в P и не в NP-полных, а в NP
У меня есть курс под названием «Анализ алгоритмов» в колледже, где мы сейчас изучаем различные классы сложности - P, NP, NP-hard и др.
Мы ' Мы уже обсуждали NP-полные проблемы как пересечение NP и NP-трудных, а также P-проблемы, содержащиеся в NP. Мы также говорили о некоторых примерах, в основном о NP-полных проблемах (k-раскраска, k-клика, SAT).
В большинстве случаев мы доказываем NP-полную задачу с помощью:
a. Нахождение недетерминированного алгоритма для ее решения (который использует выбор, успех, неудачу);
b. Сведение к ней известной NP-полной проблемы.
Дело в том, что эти проблемы, когда они выполняются на детерминированной машине (последовательно, вместо одновременного ветвления при обнаружении выбора), имеют решения с экспоненциальным временем.
Мой вопрос: this - я никогда не сталкивался с проблемами, которые нельзя было бы решить ни за полиномиальное, ни за экспоненциальное время; Задачи с полиномиальным временем относятся к P, а задачи с экспоненциальным временем обычно являются NP-полными.
Там ' http://en.wikipedia.org/wiki/Np_complete
Я хотел бы знать пример проблемы, которая не находится ни в P, ни в NP-полной, а в NP .
Кроме того, это внутренне экспоненциальные задачи, такие как создание набора мощности NP-полного набора? Или это имя применимо только к задачам, для которых используется алгоритм экспоненциального времени только потому, что нет другой очевидный метод решения?
Хорошо, поэтому я дал ответ Рошу Оксюморону , потому что он на самом деле перечислил некоторые примеры проблем, предположительно возникающих между 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-assuming-that-p-np что в целом интересно, если не совсем связано с исходным вопросом.
Большое спасибо,
Дэн