Много-одно сокращение или сокращение Тьюринга для определения NPC

39

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

Матиас
источник

Ответы:

32

Две причины:

(1) просто вопрос минимальности: быть NPC при сокращениях «многие-один» - формально более сильное утверждение, и если вы получите более сильное утверждение (как это сделал Карп и как вы почти всегда), то почему бы не сказать так?

(2) Разговор о сокращениях «многие-один» приводит к более богатой, более тонкой иерархии. Например, различие NP против co-NP исчезает при сокращениях по Тьюрингу.

По духу это похоже на то, почему часто используют сокращения Logspace, а не polytime.

Ноам
источник
16
Хотя (2), безусловно, верно, я могу использовать (1), чтобы доказать, что мы должны использовать сокращения один-один. Поскольку большинство сокращений «многие-один», которые мы строим, на самом деле являются сокращениями «один-один», почему бы нам не изучить их, когда они формально сильнее, и в любом случае мы получаем их большую часть времени? Я думаю, потому что проще не беспокоиться о доказательстве инъективности, хотя у нас это обычно бывает. В этом смысле, возможно, сокращение «один-один» является своего рода «сокращением Златовласки» - просто правильная сила, просто правильная простота доказательства.
Джошуа Грохов
21

Я не знаю, есть ли предпочтения, но предполагается, что это разные понятия. То есть сводимость по Тьюрингу считается более сильным понятием. (Там существуют А и В такие , что А является Т-сводится к B, но не мо приводимое к В.) В одном документе , который обсуждает это это один от Lutz и Mayordomo. Они предлагают усилить утверждение P! = NP; примерно, этот NP включает в себя немаловажное количество EXPTIME. Это предположение позволяет им показать, что два понятия сводимости различны.

Аарон Стерлинг
источник
17

Я думаю, что причина, по которой люди предпочитают (для начала) сокращения «один-один», является педагогической - сокращение «один-один» от А до В на самом деле является функцией струн, тогда как сокращение Тьюринга требует введения оракулов.

Обратите внимание, что редукция Кука (полиномиальное время Тьюринга) и редукция Карпа-Левина (полиномиальное время многие-один), как известно, различаются на E безусловно, Ко и Муром и отдельно Ватанабе (на что ссылаются в статье Лутца и Майордомо в ответ Аарона Стерлинга).

Джошуа Грохов
источник
7

В этом отношении сокращения Тьюринга более эффективны, чем сокращения отображений «многие-один»: Сокращения Тьюринга позволяют сопоставить язык с его дополнением. В результате это может как-то скрыть разницу между (например) NP и coNP. В оригинальной статье Кука он не смотрел на это различие (iirc Cook фактически использовал формулы DNF вместо CNF), но, вероятно, очень быстро стало ясно, что это важное разделение, и сокращение «один-один» облегчило решение этой проблемы. ,

Kurt
источник
11
Стивен Кук отметил в своем выступлении на FLoC 2010, что его статья 1971 года фактически утверждает, что она доказывает, что SAT является полным для P ^ NP при сокращениях Тьюринга ... Конечно, обычная формулировка следует из того же доказательства, так что это ситуация кто-то претендует меньше, чем они доказали! См. 4mhz.de/cook.html для повторного набора версии статьи. Кроме того, предложение «Нам не удалось добавить ни {простых чисел}, ни {изоморфных графовых пар} в [список из 4 NP-полных задач]» всегда вызывает у меня улыбку!
Андрас Саламон
5

чтобы несколько спрыгнуть под другим углом / ответить здесь AS, это открытый вопрос (также здесь ) на границах TCS, отличаются ли сокращения Кука («Тьюринга») от сокращений Карпа-Левина («многие-один»), возможно эквивалентный (главный? ключевой?) открытый вопрос разделения классов сложности. вот новый результат в этом направлении

Отделение полноты Кука от полноты Карпа-Левина при гипотезе твердости наихудшего случая / Дебазис Мандал, А. Паван, Раджесвари Венугопалан (ECCC TR14-126)

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

ВЗН
источник
4

Σ1Q .

В теории сложности также существует понятие «полиномиальная иерархия», хотя, в отличие от арифметической иерархии, она только существует. Это приводит к более тонким классификациям, чем «Трудно ли решить эту проблему, как NP?»

Дэвид Харрис
источник
3

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

Например, Неудовлетворенность завершена для NP при уменьшении Кука, но неизвестно, что она завершена для NP при сокращении Карпа. Итак, если вы докажете, что нет сокращения Карпа с SAT до UNSAT (эквивалентно с UNSAT до SAT), то вы докажете, что NP! = CoNP и, следовательно, P! = NP.

Мухаммед Аль-Туркистани
источник
Можете ли вы дать ссылку на ваше последнее предложение или объяснить его?
Tayfun Pay
2
Я объяснил свое последнее предложение.
Мухаммед Аль-Туркистани