Почему подсчет варианта сложного решения не является автоматическим?

14

Хорошо известно, что 2-SAT находится в P. Тем не менее, представляется довольно интересным, что подсчет количества решений для данной формулы 2-SAT, то есть # 2-SAT, является # P-сложным. То есть у нас есть пример проблемы, решение которой легко, а подсчет сложно.

Но рассмотрим произвольную NP-полную задачу (скажем, 3-COL). Можем ли мы сразу сказать что-нибудь о сложности его варианта счета?

На самом деле я спрашиваю: зачем нам еще одно доказательство того, что счетный вариант сложной задачи тоже # P-hard? (Иногда вы видите экономные сокращения, которые сохраняют количество решений и т. Д.). Я имею в виду, на самом деле, если бы проблема с подсчетом была легкой, вы могли бы автоматически решить проблему с решением! Так как это не может быть трудно? (ОК, может быть, это трудно, но я не уверен, какое определение трудно).

Гидеон
источник

Ответы:

15

Причина, по которой это не автоматическая теорема о том, что «решение сложно, подразумевает, что счет сложен» состоит в том, что эти два утверждения используют разные определения «трудно».

  • Решить проблему сложно, если она является NP- полной при многочленном сокращении много-один (сокращённое Карп, сокращённое отображение за полиномиальное время).

  • Проблема с подсчетом является сложной, если она # P- завершена при сокращениях Тьюринга за полиномиальное время (иначе как при уменьшении Кука).

Таким образом, если проблема решения является NP- неполной, мы знаем, что соответствующая проблема подсчета является NP- трудной, но это не определение того, что представляет собой сложная проблема подсчета. Будучи #P -полным , кажется, гораздо более сильное утверждение , чем просто NP -трудной - Тода показал , что #P -полных проблемы трудно для всей полиномиальной иерархии при рандомизированных сокращений , так как класс сложности, #P чувствует себя гораздо ближе до PSPACE чем на  НП .

Движение в направлении , противоположном, это явно верно , что, если проблема подсчета легко в том смысле, что в  ФП , то задача решения в  P . В конце концов, если вы можете эффективно рассчитывать, вы можете точно сказать, если ответ ненулевой. Однако то, что версия для подсчета «не сложная» (т. Е. Не # P- завершенная), не означает, что она «легкая» (т.  Е. В FP ). Теорема Ладнера распространяется на  #P, поэтому, если FP** # P ** тогда существует бесконечная иерархия различных классов сложности между ними, поэтому наша «не сложная» задача подсчета может быть полной для любого из этих классов и, следовательно, не может быть «легкой» (в  FP ).

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

Дэвид Ричерби
источник
В самом деле. По поводу последнего абзаца вы можете найти более подробное обсуждение этого вопроса на cstheory.stackexchange.com/q/16119/5038 .
DW
1. проблема подсчета не определена однозначно для проблемы NP, вы должны исправить верификатор для проблемы NP, прежде чем говорить о ее версии подсчета. 2. твердость в сложности - относительная трудность , а не абсолютная трудность . Поэтому, когда мы говорим, что проблема трудна, очевидный вопрос касается того, что и при каком сравнении?
Каве