«Естественные» разрешимые проблемы, которых нет в NP.

13

Каждый раз, когда я преподаю NP-Полноту, студенты спрашивают: «Есть ли проблемы, о которых известно, что они не относятся к NP?»

Как бы вы ответили? Я обычно даю им неразрешимую проблему в качестве примера, но это часто не очень хорошо получается: (а) если я дам им проблему остановки, они думают, что это какой-то тупой угловой случай, и (б) если я дам им диофантовы уравнения, они не понимаю, почему его нет в NP (вы можете проверять решения в поли-времени ... просто подключите их! Мне трудно не использовать их в этом подходе.)

Я хотел бы привести им что-то вроде QBF в качестве примера, но доказанного разделения не существует.

Предложения?

Fixee
источник
1
это должно быть CW? это большой список ...
Суреш Венкат
@Suresh, это зависит от вашего представления о естественном. Это должно быть коротким, если мы ограничимся "естественным" для студентов.
Мухаммед Аль-Туркистани
2
Игра в Го завершена. Игра жизни Конвея неразрешима (т. Е. Это эквивалент машины Тьюринга) ... это те примеры, которые вы хотели?
user834
1
Решив , если шаг является оптимальным в шахматной доске Е Х Р Т Я М Е - гр уплотнительного т р л х т е . NИксNЕИкспTяMЕ-сомпLеTе
chazisop
2
@chazisop это не известно , если правильно содержит Н Р . ЕИкспTяMЕNп
Марк Рейтблатт

Ответы:

13

Одной из возможностей является проблема, которая является EXPSPACE-полной. NP тривиально в PSPACE, который строго содержится в EXPSPACE. Одной из проблем, которая является EXPSPACE-полной, является решение, является ли регулярное выражение, допускающее возведение в степень, всем Σ* .

Суреш Венкат
источник
Что означает ваша запись ? L(р)знак равноL(рр...р)
Нил Кришнасвами,
Обобщает возведение в квадрат (беря ровно две копии). Обратите внимание, что закрытие Kleene занимает произвольно много копий
Суреш Венкат
1
Так что это так же, как L(р)знак равноNNL(рN) ? Или бесконечные повторения включены?
Нил Кришнасвами
Я не думаю, что бесконечные повторы включены.
Суреш Венкат
Спасибо и извините за ужасную педантичность. Использование обычно понятно в контексте, но у меня его не было. :)
Нил Кришнасвами
11

Так как вы подчеркиваете естественные проблемы, вот очень естественная -полная проблема, которой нет в N P : Проблема мозаичного квадрата: При заданном наборе конечных плиток, это мозаика квадраты размера 2 n x 2 n ?NEXPNп2n2N

Обратите внимание, что когда размер квадрата равен x n ( n закодирован в унарном виде), тогда проблема становится N P -полной.NNNNп

Для -полноты квадратной черепицы, проверьте ссылку.NЕИксп

[1] Христос Х. Пападимитриу. Вычислительная сложность. Аддисон-Уэсли, Рединг, Массачусетс, 1994

Мухаммед Аль-Туркистани
источник
Захватывающий. Таким образом, разбиение квадрата размером , где n представлено в унарном порядке, является NP-полным; и разбиение квадрата 2 n × 2 n , где n представлено в двоичном виде, является NEXP-полным. Это идея? Что-нибудь известно о сложности мозаики n × n?n×nn2n×2nnn×n квадрата где представлено в двоичном виде? Или вы имели в виду, что n представлено в одинарном даже для первого предложения вашего ответа? nn
DW
Да, на ваш последний вопрос.
Мухаммед Аль-Туркистани
Черепица квадрат Nexp-полнымкогда п представлено в двоичной. n×nn
Мухаммед Аль-Туркистани
10

Известно, что любая задача, полная для или 2 E X P T I M E, не существует в N P (по теореме иерархии времени). Аналогично для N E X P S P A C E и E X P S P A C ENEXPTIMEEXPTIMENPNEXPSPACEEXPSPACE(по пространственной иерархии + симуляция). Часто вы можете получить «фальшивые» проблемы с помощью отступов, но естественные проблемы, завершенные для этих классов, не кажутся настолько распространенными (вероятно, потому что они невероятно сложны!), Но вот некоторые из них:

EXPSPACE:
Регулярность эквивалентности с оператором возведения в степень

2-EXPTIME:
Удовлетворенность для CTL * (временная логика)
Удовлетворенность для ATL *
Задача решения для арифметики Пресбургера

Марк Рейтблатт
источник
3
Арифметика Сколема, которая является арифметикой с умножением, но не сложением, также разрешима. Тот факт, что вы можете решить теорию первого порядка для одного, но не для сложения и умножения, кажется мне довольно важным фактом.
Нил Кришнасвами,
4

По теореме иерархии времени , еслиграмм(N) является конструируемой во времени функцией, и е(N+1)знак равноо(грамм(N)), тогда:

NTime(е(N))NTime(грамм(N)),

Так, например, любая проблема, полная NEXP, отсутствует в NP. Ссылаясь из Википедии :

Важный набор НЕОБХОДИМЫХ полных задач относится к кратким схемам. Краткие схемы - это простые машины, используемые для описания графов в экспоненциально меньшем пространстве. Они принимают два числа вершин в качестве входных и выходных данных, есть ли между ними ребро. Если решение задачи на графе в естественном представлении, таком как матрица смежности, является NP-полным, то решение той же задачи для краткого представления схемы является NEXPTIME-полным, потому что входное значение экспоненциально меньше. В качестве одного простого примера, нахождение гамильтонова пути для закодированного таким образом графа является NEXPTIME-полным.

См. Также раздел «Краткие проблемы» на стр. 492 книги Пападимитриу .

М.С. Дусти
источник
2
Связанный: cstheory.stackexchange.com/questions/3297/…
arnab
2

Канальная система - это набор конечных автоматов с каналами связи, по которым они могут отправлять сообщения. Сообщение - это буква алфавита. В системе каналов с потерями сообщения могут быть отброшены: письмо, отправленное по каналу, может исчезнуть. Проблема достижимости для систем каналов с потерями является разрешимой, но не примитивной рекурсивностью.

Для более мягкого примера, проблема достижимости для систем сложения векторов сложна в EXPSpace.

Виджай Д
источник