Примеры задач не в P и не в NP-полных, а в NP

Question

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

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

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

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

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

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

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

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

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

2. Кроме того, существуют по существу экспоненциальные задачи, такие как генерация набора мощности набора 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-assumption-that-p-np, что в целом интересно, если не совсем связано с первоначальным вопросом.

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

Дан

Answer 1

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

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

Answer 2

1. Проблемы BQP, такие как целочисленная факторизация и дискретный логарифм (взлом RSA и DSA), как полагают, находятся за пределами P, а также предположительно находятся в NP, но не в NP-полной.Известно, что целочисленная факторизация находится в NP, и предполагается, что она находится за пределами P и NP-complete.

http://en.wikipedia.org/wiki/BQP

http://en.wikipedia.org/wiki/Integer_factorization

NP - это подмножество EXPTIME, но ожидается, что NP! = EXPTIME (то есть, проблемы, полные EXPTIME, отсутствуют в NP).Как и в случае P = NP, это еще не доказано (но известно, что P! = EXPTIME).Например, проверка того, будет ли алгоритм половинным после k шагов, является EXPTIME-полной.Найти набор мощности слишком (очевидно).

http://en.wikipedia.org/wiki/EXPTIME

Answer 3

1. Нет известных проблем в NP \ NPC.

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

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

Answer 4

Цяочу Юань , Какие существуют методы, чтобы показать, что проблема не является NP-полной ?,

может помочь.