Можно ли определить, лежит ли язык L в NP?

15

Учитывая язык L, определенный машиной Тьюринга, который его решает, возможно ли алгоритмически определить, лежит ли L в NP?

txwikinger
источник
Пересмотрен в теории сложности. Не уверен, что это имеет отношение к NP-полноте.
Арьябхата
1
FWIW, несмотря на голоса на сайте предложения, я думаю, что этот вопрос более масштабный, чем вопрос о факторинге именно потому, что вопрос о факторинге был бы рассмотрен в большинстве курсов сложности вступления, но этот вопрос даже не рассматривается во многих выпускниках. курсы сложности.
Джошуа Грохов
1
Разве это не рассматривается во вводных курсах по вычислимости как типичному применению теоремы Райс?
Мориц
3
Мориц - хотя ответ «да / нет» на этот вопрос охватывается теоремой Райс, см. Мой ответ ниже для более интересных результатов. Может быть, txwikinger, вам следует изменить вопрос на «Какова сложность множества {i: L (M_i) в NP}?»?
Джошуа Грохов
Я отвечу ответом Джошуа здесь. Ответ может быть очевидным, когда язык указан машиной Тьюринга, но ответ тот же (и, возможно, не совсем очевидный), если мы разрешаем указывать язык в каком-либо произвольном формате.
Ананд Кулькарни

Ответы:

24

Во-первых, по теореме Райс, это свойство ТМ, которое зависит только от языка, который они вычисляют, поэтому оно не может быть вычислимо.

Но, более того, известно , что индекс набор (то есть, множества ДЧ , что языки в вычислительных N P ) является Σ 0 3 -полным ( Σ 0 3 в арифметической иерархии вычислимости, не полиномиальная иерархия).NпNпΣ30Σ30

Подобные вопросы были впервые исследованы Хайеком . Для получения дополнительной информации см., Например, эту статью Кена Ригана.

Еще несколько замечательных самородков из статьи Хайека:

  • Индекс множество является Σ 0 3 -полным.пΣ30
  • является Π 0 2 -полным{я:пL(Mя)NпL(Mя)}Π20
  • Существует полная машина Тьюринга (останавливается на всех входах) , так что P L i = N P L i, но утверждение « P L i = N P L i » является независимым (где L i = L ( M i ) ) , Аналогично для Релятивизации , где Р N P .MяпLязнак равноNпLяпLязнак равноNпLяLязнак равноL(Mя)пNп
Джошуа Грохов
источник
1
Здесь вопрос представляется проблемой обещанного решения (данный язык обещается ТМ, а не только признанным), а не проблемой полного решения. Будет ли здесь применима теорема Райса? Напомним, что в доказательстве теоремы Райс используется неразрешимость остановки, поэтому неразрешимость здесь существенна.
Zeyu
2
В заданном вопросе язык L был «дан машиной, которая его решает». Так оно и было на самом деле: учитывая машину Тьюринга M, можно ли определить, находится ли L (M) в NP. Если бы язык L не был определен ТМ, а просто задан как подмножество натуральных чисел, что бы означало алгоритмически решить, находится ли L в NP? В частности, как мы можем думать о L как о входе в алгоритм, если сам L не задан конечным описанием?
Джошуа Грохов
1
Да, я знаю. Но в теореме Райса возможно, что ТМ не определяет язык, т. Е. Не вычисляет полную функцию.
Zeyu
2
Это общая эвристика, что, учитывая семантическое свойство машин Тьюринга, такое как «M определяет язык NP», нужно сначала попытаться выразить это свойство в логике первого порядка. Это помещает свойство в уровень Арифметической Иерархии; эвристика заключается в том, что свойство обычно является завершенным для этого уровня иерархии. Я хотел бы спросить, есть ли какие-нибудь заметные контрпримеры к этой эвристике.
Энди Друкер
2
Сокращение до Полиномиальной Иерархии, вещи менее вероятно будут вести себя так хорошо. Например, рассмотрим свойство «C - логическая схема минимального размера (для функции, которую она вычисляет)». Эта проблема NP-трудна и может быть помещена в Полиномиальную Иерархию, но она открыта, готова ли она к уровню, на котором она естественным образом находится. (такие результаты известны для некоторых ограниченных классов цепей, например DNF; см. обзор из двух частей "Полнота в полиномиальной иерархии" Шефера и Уманса.)
Энди Друкер,
5

Ответ на ваш буквальный вопрос - нет, как отметил Джошуа Грохув.

Однако, как заявил Хольгер, можно в линейное время проверить, «недетерминирован ли машина Тьюринга (NTM)» самосинхронизируется и останавливается после n ^ k шагов для некоторой константы k, с помощью некоторого стандартного способа моделирования часов (таких как код ниже). Часто, когда статья или книга предполагают (неправильно), что можно определить, является ли NTM полиномиальным временем, это то, что они действительно имеют в виду. Возможно, именно поэтому вы задали вопрос? (У меня был тот же вопрос, когда я впервые изучил теорию сложности и где-то увидел утверждение о том, что можно проверить, является ли ТМ многопоточным.) Реальный вопрос заключается в том, почему кто-то может захотеть сделать это, и я расскажу ниже после объяснения как .

Есть много способов добавить такую ​​функцию часов. Например, представьте на входе x длину n, поочередно выполняя одну инструкцию тактируемого «первичного алгоритма», а затем одну инструкцию следующего алгоритма, которая заканчивается (что-то близкое к) n ^ k шагов:

для i_1 = 1 до n
  для i_2 = 1 до n
...
        для i_k = 1 до n
          нет-оп;
возвращение;

Если приведенный выше код возвращается до остановки основного алгоритма, то остановите все вычисления (скажем, с отклонением).

Алгоритм, который решает, имеет ли NTM такую ​​форму, если интерпретировать его как попытку алгоритма определить, является ли его входной сигнал многовременным NTM, сообщит о ложных отрицаниях: некоторые NTM гарантированно останавливаются за полиномиальное время, даже если они не чередуют выполнение одного оператора алгоритма с одним оператором часов, как в приведенном выше коде (следовательно, они будут отклонены, несмотря на то, что они имеют многократное время).

Но нет ложных срабатываний. Если NTM проходит тест, то он определенно останавливается за полиномиальное время, следовательно, он определяет некоторый язык NP. Однако, возможно, поведение его основного первичного алгоритма изменяется, если часы иногда заканчиваются до того, как первичный алгоритм останавливается, вызывая отклонение вычислений, даже если первичный алгоритм мог бы принять, если дать достаточно времени для завершения. Поэтому решаемый язык может отличаться от языка основного алгоритма. Нои это является ключевым, если выполняемый основной алгоритм на самом деле является алгоритмом полиномиального времени, работающим в момент времени p (n), и если постоянная k в часах достаточно велика, чтобы n ^ k> p (n), то основной алгоритм всегда останавливается до истечения времени. В этом случае ответ основного алгоритма не изменяется, поэтому основной алгоритм и синхронизированный NTM, имитирующий его, выбирают один и тот же язык NP.

Почему это важно? Это означает, что можно «перечислить все языки NP» (которые, как я сказал, в литературе часто неточно обозначаются как «решить, является ли данный NTM многовременным» или «перечислить все многовременные NTM»). Точнее, можно перечислить бесконечный список NTM M_1 M_2, ..., со свойствами, которые

  1. Каждый M_k выполняется за полиномиальное время (например, путем присоединения ^ k-часов к M_k), следовательно, решает некоторый язык NP, и
  2. Каждый язык NP является языком, выбранным некоторыми M_i из списка.

Чего не происходит, так это того, что каждый NTM за полиномиальное время находится в списке. Но каждый язык NP имеет бесконечное количество NTM, представляющих его. Таким образом, каждый NP-язык гарантированно имеет по крайней мере некоторые из своих репрезентативных NTM в списке, в частности, все эти NTM с достаточно большим индексом k, который n ^ k превышает время работы M_k.

Это полезно для выполнения трюков типа диагонализации, которые требуют алгоритмического перечисления таких бесконечных (или неограниченных) списков всех языков NP. И, конечно же, все это обсуждение применимо ко многим другим типам машин, кроме многополосных NTM, таких как поливременные детерминированные TM.

Дейв Доти
источник
3

п(N)

Holger
источник
2
Это работает, только если это тактовая недетерминированная ТМ. Если я просто дам вам синхронизированную ТМ (даже та, которая работает в экспоненциальном времени), все равно не будет решено, будет ли язык, который он решит, использовать в NP. Однако, если N_1, N_2, ... - это перечисление ТМ с экспоненциальными часами, множество {i: L (N_i) в NP}, вероятно, больше не является Sigma_3-полным, поскольку вы уже гарантировано, что N_i Всего, но это все еще, конечно, не вычислимо.
Джошуа Грохов