Каждая NP-сложная задача вычислима?

Ответы:

15

Нет, проблема NP -hard не должна быть вычислимой. Определение является довольно полным: проблема L является NP трудной, если эта проблема, имеющая решение за многократное время, подразумевает, что каждая проблема в NP имеет решение за многократное время (то есть сокращение до L существует для каждой проблемы в NP .).

В этом случае неисчислимые задачи оказываются бессмысленными: предположим, мы могли бы решить их за полиномиальное время. Затем мы используем доказательство того, что это не вычислимо, чтобы получить, что это и вычислимо, и не вычислимо, противоречие. Из этой лжи мы можем вывести что угодно, а именно, что есть алгоритм полиномиального времени для любой задачи NP мы рассматриваем.

Например, рассмотрим проблемы остановки H . Мы можем уменьшить любой язык A до H следующим образом, предполагая, что у нас есть проверка на полимеризацию f ( s , c ), которая проверяет, является ли c сертификатом для s A :NPAHf(s,c)csA

  • С учетом ввода s
  • Construct (но не запускать) машина Тьюринга M , которая принимает входной x пытается каждый сертификат c и привалы , если c это сертификат , подтверждающий , что sA .
  • Вернуть (то есть вернуть true, если M останавливается на входе x )H(M,x)Mx

Таким образом, с помощью одного вызова многочастичного алгоритма, решающего проблему остановки, мы можем решить любую задачу за полиномиальное время.NP

Такое сокращение бесполезно, потому что все, что он делает, говорит, если «если ложь, то что-то». Мы уже знаем, что не существует алгоритма polytime для неисчислимых задач.

jmite
источник
7
«Определение довольно полное», но это не то, что следует из этой цитаты в вашем ответе.
У меня есть вопрос по этому поводу. Я могу представить себе функцию, которая решает проблему остановки для самого большого набора программ, возможного при некоторых соответствующих ограничениях, но я могу представить, что эта функция все еще не вычислима (в том смысле, что мы никогда не найдем ее даже при бесконечном количестве времени) , Тем не менее , если мы как - то же есть решение к этому, это даже не ясно мне , что он должен решить все NP-трудные задачи обязательно. Так что либо логика в этом ответе не соответствует (имеется в виду неразрешимое! = Не вычислимо), либо мои рассуждения ошибочны (вероятно). Так в чем же недостаток?
Мердад
12
Большая часть этого ответа неверна, включая ваше определение NP hard: задача A - NP hard, если, «для каждой проблемы NP B сокращение множителя B до A.» Это не то же самое, что «если A - многовременность, то P = NP». (Последнее является следствием первого, но не наоборот.) В частности, есть почти наверняка невычислимые проблемы, которые также не могут быть NP сложными. Я не проработал детали, но проблема членства в достаточно общем наборе (в смысле принуждения) должна сработать. Набор остановки, в частности, NP-труден, однако, по вашему уменьшению.
7
Подумайте о сокращении времени от A до B следующим образом: это программа, которая выполняется за полиномиальное время, но у нее есть особая возможность за один шаг запросить оракула, который отвечает на случаи проблемы B. Независимо от того, для B существует алгоритм с разным временем, или даже если B вычислимо, все равно имеет смысл задать следующий вопрос: если предположить, что оракул правильно отвечает на заданные вопросы (за один шаг), отвечает ли рассматриваемая программа запустить за полиномиальное время и правильно решить случаи проблемы A?
2
@MikeHaskel Ваша аналогия с оракулом верна только в том случае, если после запроса к оракулу программа должна остановиться с тем же ответом, что и этот оракул. В противном случае co-SAT сводится к SAT: запрашивайте оракула и отрицайте. В некоторых понятиях сокращения, например, при уменьшении по Тьюрингу, это было бы приемлемо, но при стандартном сокращении по времени и даже при сокращении по многим показателям это не так.
Чи
16

Похоже, что в этом сообществе существует некоторая путаница по этому вопросу. Я дам подробный ответ в надежде очистить воду и осветить взаимосвязь между вычислимостью и NP-твердостью.

Во-первых, я полагаю, что ясность и ясность в отношении различных определений решит большую часть путаницы.

Строка представляет собой конечную последовательность символов из некоторого фиксированного конечного алфавита.

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

Предположим , у нас есть две проблемы , решения, и B . Скажем является полиномиальным временем приводимым к B , если существует некоторый многочлен р ( х ) и алгоритм некоторый алгоритм М такое , что для всех строк ы ,ABABp(x)Ms

  • Если вы передаете ввод s , M останавливается менее чем за p ( | s | ) шагов (где | s | - длина строки s ) и выводит строку M ( s ) .MsMp(|s|)|s|sM(s)
  • в А тогда и только тогдакогда M ( ы ) в B .sAM(s)B

Проблема Решение является NP-трудной , если для каждого НП проблемы решения A , полиномиально сводится к B .BAAB

Решение задачи вычислимо, если существует алгоритм , который для всех строк s ,Ms

  • Если вы предоставляете вход s , M останавливает и выводит либо «да», либо «нет».MsM
  • Выход «да», если в A и «нет» в противном случае.sA

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


Это оставляет два вопроса на столе:

  1. Определения оставляют открытой возможность того, что невычислимые функции могут быть NP-сложными. Есть ли на самом деле невычислимые NP-сложные функции?
  2. Существует интуиция, что сказать, что проблема NP-hard, значит сказать, что ее трудно решить. Сказать, что это не вычислимо, все равно, что сказать, что «действительно трудно» решить. Итак, все ли невычислимые задачи NP-сложны?

На вопрос 1 легче ответить. Есть два особенно важных способа найти невычислимые проблемы решения, которые являются NP-сложными. Первая проблема остановки: Проблема Остановки, , обладает свойством , что каждая вычислимая проблема решения полиномиально сводится к H . Поскольку проблемы NP вычислимы каждая задача NP полиномиально сводится к H , поэтому H является NP-трудной.ЧАСЧАСЧАСЧАС

Другой важный способ построения невычислимой NP-сложной задачи состоит в том, чтобы заметить, что мы можем объединить любую известную NP-сложную проблему с любой известной невычислимой проблемой. Пусть NP-труден, а B невычислим. Сформируйте решение задачи A B следующим образом: A B содержит строки вида «0, за которыми следует строка в A » и строки вида «1, за которыми следует строка в B ». A B является NP-трудным, потому что мы можем превратить любое уменьшение (любой проблемы) в A в уменьшение к A BAВAВABABABAAB: просто настроить алгоритм для вывода дополнительного «0» в начале его выходной строки. B не является вычислимой, поскольку вычисление A B требует принятия решения , какие строки , которые начинаются с «1» в наборе; это невозможно, так как B не вычислимо.ABABB


Вопрос 2 значительно сложнее, но на самом деле существуют невычислимые задачи решения, которые не являются NP-сложными (при условии, что P NP). Прекрасный ответ Ювала создает такую ​​проблему решения в явном виде. (Для любого теоретика вычислимости в комнате любой " родовой Cohen 1 0 1 " также поможет.) Я расскажу, почему интуиция "NP-сложные задачи сложна, невычислимые задачи сложнее". " неправильно.Π10

NP-твердость и невычислимость говорят о том, что проблема является «сложной» в очень общем смысле, но они очень разные и не должны смешиваться как одно и то же явление. В частности, NP-жесткость является «положительным» свойством: NP-сложная задача трудна в том смысле, что, имея доступ к шпаргалке для A , вы можете решить сложный класс задачAA . С другой стороны, не вычислимости «негативный» свойство: не-вычислимая проблема трудно в том смысле , что вы не можете решить А с данным классом ресурсовAA .

( «Принуждение», кстати, является методом , используемым для получения «Коэн родового» , что я говорил. Чтобы быть очень очень расплывчато, заставляя это общий способом производства вещей , которые являются «общими» в том , что они имеют нет положительных свойств и каждого отрицательного свойства. Вот почему форсирование может напрямую привести к проблеме, которая не является ни вычислимой, ни NP-трудной.)Π10

Сообщество
источник
2
Разве вы не можете построить неразрешимый язык, который не сложен по диагонали? Диагонализировать против всех решателей и всех сокращений polytime от SAT.
Юваль Фильмус
1
@YuvalFilmus Это, вероятно, работает, да. Я думаю, что написание подробностей о том, почему диагонализация по сравнению с многопоточным сокращением из SAT является возможным количеством, похоже на то, чтобы показать, что форсирование работает, поэтому я не думал об этом в этих терминах.
1
@YuvalFilmus Я также добавил пояснение только сейчас, что вы должны предполагать P NP: в моем доказательстве определенно был шаг, который гласил: «Возьми некоторую проблему в NP, но не в P.»
1
@aelguindy Я не уверен, какой самый доступный способ доказать это. Я упомянул технику принуждения , которая очень общая и мощная. Я узнал об этом от людей, а не от учебников, так что лично я не знаю, что такое «принуждение». Однако, как отметил Ювал, форсирование, вероятно, излишне: возможно, работает более прямой аргумент, связанный с диагонализацией. «Рекурсивно перечислимые множества и степени» Соаре - это учебник, который охватывает большую часть этого стиля аргументации, если вы хотите с ним ознакомиться. Опять же, большая часть этого, вероятно, излишня. ...
1
@aelguindy Кроме того, если вы думаете о наборе решений проблем как о топологическом пространстве, вы можете, вероятно, массажировать теорему категории Бэра, чтобы получить доказательство. Эта теорема тесно связана с принуждением, но она более старая и более простая.
11

Нет. NP-Hard означает, что он такой же сложный или сложный, как самые сложные NP-проблемы. Интуитивно понятно, что быть неисчислимым намного сложнее, чем NP.

Википедия:

Есть проблемы с решением, которые являются NP-сложными, но не NP-завершенными, например, проблема остановки.

Все знают, что это не вычислимо

Разрушаемый Лимон
источник
4
Обратите внимание, что хотя некоторые невычислимые задачи (например, проблема остановки) являются NP-сложными, это не означает, что все невычислимые задачи являются NP-сложными. Смотрите мои комментарии к ответу jmite. NP-твердость является положительным свойством: оно говорит о том, что ответы на вашу проблему могут помочь решить проблемы NP. Быть NP-hard подразумевает, что проблема в некоторой степени сложная. Не все сложные проблемы являются NP-сложными.
@MikeHaskel: Наличие решения проблемы остановки сводит все проблемы к P * сложности проблемы остановки ..
Джошуа
1
@ Джошуа: Это не имеет смысла. Это как фрагмент не-доказательства. Что вы имеете в виду, когда задача имеет конечное число бит в своем решении, и почему вы думаете, что это применимо ко всем неисчислимым задачам? Что вы имеете в виду под "P * halts"? Что остальное в "уменьшить через n-й бит ..."?
user2357112 поддерживает Monica
1
@ Джошуа: Похоже, основная проблема в том, что вы предполагаете, что каждая проблема соответствует машине Тьюринга. Не каждая проблема соответствует машине Тьюринга. Там нет problem()функции, которую мы можем вызвать.
user2357112 поддерживает Monica
1
Вы, вероятно, должны переместить это в чат или что-то
Разрушаемый Лимон
9

Для полноты приведем следующую теорему:

Существует невычислимый язык, который не является NP-сложным тогда и только тогда, когда P NP.

Если P = NP, то любой нетривиальный язык (отличающийся от ) является NP-сложным (упражнение), и, в частности, любой невычислимый язык является NP-сложным.,{0,1}

Теперь предположим, что P NP. Пусть T i будет некоторым перечислением всех машин Тьюринга. Мы будем строить необходимый язык L поэтапно. На каждом этапе мы будем держать { 0 , 1 , ? } раскраска { 0 , 1 } ∗, которую мы также обозначим через L ; здесь 0 означает, что мы решили, что строка находится не в L , 1 означает, что мы решили, что строка находится в L , и ?TiL{0,1,?}{0,1}L0L1L?означает, что мы еще не решили. Все, кроме конечного числа строк будут окрашены ,?

На шаге мы думаем о T i как о машине, которая либо принимает свой ввод, отклоняет его или никогда не останавливается. Если T i не всегда останавливается, то мы ничего не делаем. Если T i всегда останавливается, мы находим строку x такую, что L ( x ) = ? и установите L ( x ) : = 0, если T i ( x ) принимает, и L ( x ) : = 1, если T2iTiTiTixL(x)=?L(x):=0Ti(x)L(x):=1 отклоняет.Ti(x)

На шаге мы рассматриваем T i как машину, вычисляющую (возможно) частичную функцию на своем входе. Если T i не является итоговым, или если оно итоговое, но не выполняется за полиномиальное время, или если оно итоговое, но его диапазон конечен, мы ничего не делаем. Если T i является полным, выполняется за полиномиальное время и имеет бесконечный диапазон, то мы находим строку x такую, что L ( T i ( x ) ) = ? , Если x S A T (то есть, если x2i+1TiTiTixL(Ti(x))=?xSATx encodes a satisfiable CNF) then we set L(x):=0, and otherwise we set L(x):=1.

After infinitely many steps, we get a {0,1,?} coloring of {0,1} which we complete to an actual language in an arbitrary way.

The resulting language L isn't computable: step 2i ensures that Ti doesn't compute it. It also isn't NP-hard, but here the reasoning is a bit more delicate. Suppose that Ti is a polytime reduction from SAT to L. If the range of Ti is finite then we can turn Ti into a polytime machine deciding SAT, by listing the truth table of L on the range of Ti. This is impossible by the assumption PNP. Thus Ti has infinite range, but then step 2i+1 rules out its being a reduction from SAT to L.

Yuval Filmus
источник
3

A language L is NP-hard if for every LNP we have that L is polynomial-time reducible to L. The acceptance problem for nondeterministic Turing machines

ANTM={M,wM is a nondeterministic Turing machine that accepts w}

is undecidable and is NP-hard. For consider an LNP. L is decided by some nondeterministic Turing machine M with polynomial time complexity. A poly-time reduction f from L to ANTM is given by

f(x)=M,x
Hans Hüttel
источник
3

Я думаю, что заставляет людей думать, что не существует неисчислимой NP-трудной проблемы, так это то, что они упускают момент, когда NP-твердость является нижней границей сложности проблемы, а не верхней границей их твердости, такой как P или NP.

Язык L, являющийся NP-сложным, означает, что он выше языка в NP, и это так. Теперь, если вы понимаете это, нужно показать, что существуют произвольно более сложные проблемы.

Позволять Aбыть языком Рассмотрим алгоритмы, дополненные черным ящиком, которые они могут использовать для определения членства вA, Давайте обозначим их какСA, Легко видеть, что проблема остановки дляСA, ЧАСaLTСA не в СA,

В теории computablity это называется переход изA и обозначается A', ТакA<A'строго. И ничто не мешает нам повторить это: A<A'<A"<A'' '<,..

Kaveh
источник