Почему большинство людей предпочитают использовать сокращения «один-один» для определения NP-полноты вместо, например, сокращений Тьюринга?
39
Почему большинство людей предпочитают использовать сокращения «один-один» для определения NP-полноты вместо, например, сокращений Тьюринга?
Две причины:
(1) просто вопрос минимальности: быть NPC при сокращениях «многие-один» - формально более сильное утверждение, и если вы получите более сильное утверждение (как это сделал Карп и как вы почти всегда), то почему бы не сказать так?
(2) Разговор о сокращениях «многие-один» приводит к более богатой, более тонкой иерархии. Например, различие NP против co-NP исчезает при сокращениях по Тьюрингу.
По духу это похоже на то, почему часто используют сокращения Logspace, а не polytime.
Я не знаю, есть ли предпочтения, но предполагается, что это разные понятия. То есть сводимость по Тьюрингу считается более сильным понятием. (Там существуют А и В такие , что А является Т-сводится к B, но не мо приводимое к В.) В одном документе , который обсуждает это это один от Lutz и Mayordomo. Они предлагают усилить утверждение P! = NP; примерно, этот NP включает в себя немаловажное количество EXPTIME. Это предположение позволяет им показать, что два понятия сводимости различны.
источник
Я думаю, что причина, по которой люди предпочитают (для начала) сокращения «один-один», является педагогической - сокращение «один-один» от А до В на самом деле является функцией струн, тогда как сокращение Тьюринга требует введения оракулов.
Обратите внимание, что редукция Кука (полиномиальное время Тьюринга) и редукция Карпа-Левина (полиномиальное время многие-один), как известно, различаются на E безусловно, Ко и Муром и отдельно Ватанабе (на что ссылаются в статье Лутца и Майордомо в ответ Аарона Стерлинга).
источник
В этом отношении сокращения Тьюринга более эффективны, чем сокращения отображений «многие-один»: Сокращения Тьюринга позволяют сопоставить язык с его дополнением. В результате это может как-то скрыть разницу между (например) NP и coNP. В оригинальной статье Кука он не смотрел на это различие (iirc Cook фактически использовал формулы DNF вместо CNF), но, вероятно, очень быстро стало ясно, что это важное разделение, и сокращение «один-один» облегчило решение этой проблемы. ,
источник
чтобы несколько спрыгнуть под другим углом / ответить здесь AS, это открытый вопрос (также здесь ) на границах TCS, отличаются ли сокращения Кука («Тьюринга») от сокращений Карпа-Левина («многие-один»), возможно эквивалентный (главный? ключевой?) открытый вопрос разделения классов сложности. вот новый результат в этом направлении
Отделение полноты Кука от полноты Карпа-Левина при гипотезе твердости наихудшего случая / Дебазис Мандал, А. Паван, Раджесвари Венугопалан (ECCC TR14-126)
источник
В теории сложности также существует понятие «полиномиальная иерархия», хотя, в отличие от арифметической иерархии, она только существует. Это приводит к более тонким классификациям, чем «Трудно ли решить эту проблему, как NP?»
источник
Как правило, сокращение «многие-один» (Karp) легче спроектировать, поскольку это ограниченная форма сокращения, которая выполняет один вызов, а основная задача заключается в преобразовании ввода в другое кодирование. Сокращение Тьюринга может включать сложную логику. Наличие набора, который является полным для NP при сокращении по Тьюрингу, но не при сокращении много-один, означает, что P! = NP.
Например, Неудовлетворенность завершена для NP при уменьшении Кука, но неизвестно, что она завершена для NP при сокращении Карпа. Итак, если вы докажете, что нет сокращения Карпа с SAT до UNSAT (эквивалентно с UNSAT до SAT), то вы докажете, что NP! = CoNP и, следовательно, P! = NP.
источник