Что мы знаем о фазовом переходе задач # P-Complete?

11

Что известно о фазовом переходе в задачах # P-Complete? В частности, существует ли другой фазовый переход для # DNF-k-SAT и # CNF-k-SAT?

Обновление:
Как мы знаем, в Random k-SAT есть фазовый переход, где решение проблемы переходит от простого к сложному и снова к легкому. Я хотел бы знать, существует ли такое явление и для проблем # P-Complete. Что еще более важно, если существует фазовый переход, то же самое для # CNF-k-SAT и # DNF-k-SAT?

Я думаю, что есть какой-то тип фазового перехода для # CNF-k-SAT. С другой стороны, я не думаю, что есть фазовый переход для # DNF-k-SAT, и проблема усложняется, когда мы добавляем больше предложений ....

cc.complexity-theory counting-complexity phase-transition Тайфун Пей
источник
1
Не могли бы вы уточнить, что вы подразумеваете под "фазовым переходом #P"? Фазовый переход для задач NP-Complete обычно принимается равным вероятности того, что случайный случай, полученный из некоторого параметризованного распределения, будет удовлетворительным (скажем, для 3-SAT). Что такое переход для #P? Когда определенный процент выполним?
user834
Также укажите, пытаетесь ли вы вычислить точное значение или допускаете приблизительные значения.
Тайсон Уильямс
1
"проблема переходит от простого к сложному и снова к трудному" Вы имеете в виду "от простого к сложному и снова к легкому"?
Тайсон Уильямс
1
Мне все еще неясно, какое количество вы измеряете. Фазовый переход 3-SAT (в качестве примера для конкретности) принимается за вероятность существующего решения. т.е. хотя бы одно решение существует. Таким образом, если переход "#P" означает вероятность ненулевого числа решений, то эти два эквивалентны. Кроме того, существует различие между «легким» и «существующим решением», поскольку первое подразумевает полиномиальный алгоритм, а второе - нет. АЭС печально известна трудностью почти везде, даже далеко от точки перехода.
user834

Ответы:

7

Для подсчета независимых множеств есть недавнее доказательство вычислительного фазового перехода, Аллан Слай: http://arxiv.org/abs/1005.5584 (алгоритм Дрор Вейц из 2006 года; Аллан доказал соответствие твердости и соавтор за это лучшая бумажная награда в FOCS'10)

Обратите внимание, что для случайных 3SAT и подобных задач нет никаких доказательств того, что эти проблемы действительно трудны в соответствующем интервале. Когда вы идете к сложным подсчетам проблем, становится легче доказать твердость.

Дана Мошковиц
источник