Подтвердить что ты не робот

Примеры проблем не в P, ни в NP-полном, но в NP

У меня есть курс под названием "Анализ алгоритмов" в колледже, где мы в настоящее время изучаем различные классы сложности - P, NP, NP-hard и т.д.

Мы уже обсуждали NP-полные проблемы как пересечение NP и NP-hard, а также проблемы P, содержащиеся в NP. Мы также говорили о некоторых примерах, в основном о NP-полных проблемах (k-coloring, k-clique, SAT).

В большинстве случаев мы доказываем, что проблема NP-полная:

а. Поиск недетерминированного алгоритма для его решения (который использует выбор, успех, сбой);

б. Сокращение известной проблемы NP-полной.

Дело в том, что эти проблемы при запуске на детерминированной машине (последовательно, вместо одновременного разветвления при встрече с выбором) имеют экспоненциально-временные решения.

Мой вопрос в том, что я никогда не сталкивался с проблемами, которые решались ни в полиномиальное время, ни в экспоненциальном времени; полиномиальные временные задачи находятся в P, а проблемы экспоненциального времени обычно находятся в NP-полном.

Здесь есть полезная диаграмма Венна: http://en.wikipedia.org/wiki/Np_complete

  • Я хотел бы знать пример проблемы, которая не находится ни в P, ни в NP-complete, но в NP.

  • Кроме того, являются внутренне экспоненциальные проблемы, такие как генерирование набора мощности набора NP-complete?. Или это имя применяется только для задач, для которых используется алгоритм экспоненциального времени, только потому, что нет другого очевидного метода его решения?

Хорошо, поэтому я дал ответ Рош Оксюморону, потому что он фактически перечислял некоторые примеры проблем, которые предположительно находились между P и NPC. Спасибо за помощь, ребята, и я действительно заметил, что поставил этот вопрос не в том месте. Там также: https://cstheory.stackexchange.com/

где я нашел следующие очень полезные ответы на мой вопрос: https://cstheory.stackexchange.com/info/79/problems-between-p-and-npc который конкретно касается того, что я спросил, и: https://cstheory.stackexchange.com/info/52/hierarchies-in-np-under-the-assumption-that-p-np что обычно интересно, если не точно связано с начальным вопросом.

Большое спасибо,

Dan

4b9b3361

ОТВЕТЫ

Ответ 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

Ответ 2

Я хотел бы узнать пример проблемы, которая не входит ни в P, ни в NP-complete, но в NP.

Я тоже; если вы найдете один идите на эту веб-страницу, чтобы получить свой выигрыш в размере 1 млн долларов: http://www.claymath.org/millennium/P_vs_NP/

Ответ 3

  • Неизвестно, что в NP \ NPC нет проблемы.

  • Проблема в NP тогда и только тогда, когда недетерминированная машина turing может решить ее в полиномиальное время (или, что то же самое, детерминированная машина turing может решить ее в полиномиальное время). Это не относится к вашему примеру.

    Далее следует отметить, что мы не знаем, существует ли P = NP, поэтому вполне возможно (если маловероятно), что все проблемы в NP могут быть решены за полиномиальное время. Поэтому, если мы знаем, что проблема не может быть решена в полиномиальное время, эта проблема либо не находится в NP, либо, если мы можем доказать, что она действительно находится в NP, мы просто показали, что NP != P.