Многочисленные сокращения и сокращения Тьюринга определяют одного и того же класса NPC

11

Интересно, равны ли классы NPC, определенные сокращениями «многие-один» и сокращениями Тьюринга?

Редактировать: Другой вопрос, являются ли сокращения Тьюринга только свертыванием классов C и co-C для некоторого C или существует класс такой как существует проблема не в при сокращении Карпа, а в в сокращении Тьюринга ?C ∪ c o - C CCC∪co−CC

cc.complexity-theory np-hardness reductions Людовик Патей
источник
4
Вы читали en.wikipedia.org/wiki/… ?
Юкка Суомела
Спасибо за вашу ссылку. Он отвечает на первую часть моего вопроса, но не отвечает, есть ли проблемы, которых нет в со-С при сокращении многие-один, а в С - при сокращении по Тьюрингу, для любого С.
Людовик Пати
1
Извините, это может показаться элементарным вопросом, или, может быть, я не думаю прямо в этот поздний час, но я что-то упустил в статье в вики. В статье говорится, что при сокращениях Кука NP-complete равно co-NP-complete, но я этого не вижу. NP-hard равняется co-NP-hard по отношению к уменьшению Кука, но NP-complete означает быть NP-hard и NP , и я не понимаю, почему (например) TAUT будет в NP? Т.е. TAUT является со-NP-сложным при сокращениях Кука, но этого недостаточно для NP-завершения.
Каве
@Monoid, вы должны переформулировать свой вопрос, чтобы отразить это разъяснение. Таким образом, вопрос неоднозначен
Суреш Венкат
возможное дублирование сокращений
Суреш Венкат

Ответы:

7

Посмотрите на этот вопрос и особенно на этот ответ Аарона Стерлинга. Короче говоря: «они предполагаются, чтобы быть различными понятиями».

Матиас
источник
Я знаю, что если NP! = Co-NP, то это разные понятия, потому что сокращение Тьюринга разрушает их, но могут быть различия, которые не будут разрушаться, например, проблема в NPI при сокращении «многие-один» и в NPC при сокращении Тьюринга ?
Людовик Пати
@ Monoïd: NP ≠ coNP не подразумевает (по крайней мере очевидным образом), что два понятия сокращений различны. Я боюсь, что вы путаете класс NP (который определяется независимо от выбора понятия сокращений) с классом задач решения, сводимых к NP (который зависит от выбора понятия сокращений).
Цуёси Ито
К сожалению, мой предыдущий комментарий был неверным. Если NP ≠ coNP, два понятия сокращений явно различны (SAT безусловно сводится к UNSAT по Тьюрингу, но SAT сводится к UNSAT по многим единицам тогда и только тогда, когда NP = coNP).
Цуёси Ито
9

Насколько я могу судить, этот вопрос действительно состоит из двух отдельных вопросов, первый из которых появляется в заголовке, а второй - после редактирования.

(1) Определяют ли сокращения «один-один» и сокращения Тьюринга один и тот же набор NP-полных задач (т. Е. Проблем, которые существуют как в NP, так и в какую SAT можно сократить)? То, был ли NPC при сокращениях по Тьюрингу таким же, как NPC при сокращениях «многие-один», все еще оставалось открытой проблемой семь лет назад, и я не верю, что он был закрыт с тех пор. Подробности смотрите в обзоре новостей ACM SIGACT за июнь 2003 года.

(2) К какому классу проблем относится SAT к сокращению по Тьюрингу и наоборот? Это класс NP-сложных задач (при сокращениях Тьюринга), которые находятся в P NP . Для получения дополнительной информации см. Ответ Ноама.

Питер Шор
источник
ссылка не работает.
T ....
8

Это не отвечает на ваш вопрос, но можно задать тот же вопрос для более слабых сокращений. Например, меняется ли набор проблем с NP-полнотой, если мы разрешаем только сокращение пространства журнала, или только сокращение AC 0 , или даже сокращение NC 0 . Удивительным фактом является то, что все известные NP-полные проблемы завершены даже при сокращении NC 0 .

Ссылка: Агравал М., Аллендер Э., Рудич С. 1997 г. Сокращение сложности цепей: теорема об изоморфизме и теорема о разрыве.

Робин Котари
источник
Этот вопрос о более слабых сокращениях все еще открыт? Если у меня есть проблема, когда NP был завершен при P / poly или BPP-сокращениях, но, очевидно, не при P-сокращениях без предположения о бездоказательных теоретико-числовых предположениях, стоит ли это делать?
Питер Шор
@Peter: В статье, которую я цитировал, она остается открытой, если есть какая-либо проблема, являющаяся NP-полной при полиномиальном сокращении времени, которая не является NP-полной при сокращении AC ^ 0. На этот вопрос был дан ответ Уменьшение сложности сокращений . Они показывают проблему, которая является NP-полной с сокращениями ACC, но не сокращениями AC ^ 0. Ни в одной из этих работ, по-видимому, не комментируются проблемы, являющиеся NP-полными при сокращениях, более сильных, чем полиномиальное время, и то, как это связано с возможностью быть NP-полными при сокращениях множителей.
Робин Котари
1

В настоящем документе требование , чтобы показать , что существование TF N EExP проблемы , которая
[достаточно трудно решить с нулевой ошибкой в худшем случае] предполагает существование
«Тьюринг полного языка для NP , что не правда стола полного для NP. "

С другой стороны, я не пытался прочитать ни одно из их заявленных доказательств этого результата,
но Предложение 2 и / или его доказательство демонстрируют (-ют) недопонимание определения ZPP :
кажется, что они действительно нуждаются в " FP может решить все F ЗПП», а не просто„ЗПП = Р“.


источник