Выше #P и подсчета поисковых проблем

14

Я читал статью в Википедии о проблеме восьми королев. Установлено, что не существует известной формулы для точного числа решений. После некоторых поисков я нашел статью под названием «О сложности подсчета проблем полных отображений». В этой статье есть проблема, показанная не более, чем #queens, которая выходит за пределы #P. Если взглянуть на числа #queens, которые в статье в Википедии исчерпывающе подсчитаны, они кажутся в значительной степени супер экспоненциальными.

Я хочу спросить, есть ли имя для этого класса или вообще есть ли проблемы с подсчетом, принадлежащие классам выше #P (с решением не в PSPACE, конечно, потому что это было бы очевидно).

Наконец, я хочу спросить, есть ли какие-либо другие известные результаты для других проблем поиска, таких как, например, нахождение трехцветной точки в лемме Спернера (PPAD complete).

Paramar
источник
Может быть полезно: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.989
Маркус Блезер

Ответы:

14

Если функция f находится в #P, то при заданной входной строке x некоторой длины N значение f (x) является неотрицательным числом, ограниченным . (Это следует из определения с точки зрения количества принимающих путей верификатора NP.)2poly(N)

Это означает , что многие функции F лежат вне #P для неинтересных причин --- либо потому , что е является отрицательным, или, в случае , если вы упоминаете, потому что функция растет быстрее , чем . Но для проблемы n- kens, смоделированной в статье, это всего лишь артефакт решения авторов о том, что входное значение n должно быть закодировано в двоичном виде. Если ожидаемым вводом была одинарная строка 1 n , то2poly(N)nn1n (число действительных nf(1n):=n-queen конфигурации), безусловно, будет в #P, с помощью простого верификатора NP, который проверяет правильность данной конфигурации.

Если вы хотите изучить некоторые функции, которые (предположительно) лежат за пределами #P по более интересным причинам, рассмотрите, например, эти:

  • UNSAT: если ψ - неудовлетворительная булева формула, в противном случае f ( ψ ) : = 0f(ψ):=1ψf(ψ):=0 . Эта функция отсутствует в #P, если только NP = coNP. Вероятно, это не относится к более общему классу подсчета GapP; то есть UNSAT, вероятно, не является разницей f - g двух функций #P. Однако он заключается в более общем классе сложности счета , который фактически содержит всю полиномиальную иерархию по теореме Тоды.P#P

Вам может не понравиться этот пример, потому что это не естественная «проблема подсчета». Но следующие два будут:

  • количество назначений для x, такое, что булева формула ψ ( x , ) выполнима для некоторого значения y .f(ψ(x,y)):=xψ(x,)y

  • число x такое, что, по крайней мере, для половины всех y , ψ ( xf(ψ(x,y)):=xy .ψ(x,y)=1

Последние две проблемы, как известно, не являются эффективно вычисляемыми даже при доступе оракула к #P. Тем не менее, они вычислимы в рамках так называемой «иерархии подсчета». Для некоторых более естественных проблем, классифицированных в этом классе, см., Например, эту недавнюю статью.

Подсчет равновесий по Нэшу, по-видимому, очень сложен, смотрите здесь . Кроме того, даже проблемы, в которых проблема поиска проста, трудно подсчитать, например, подсчет идеальных совпадений.

Энди Друкер
источник
1
Для вашего примера UNSAT, если он находится в GapP, вы получаете, что coNP находится в SPP, и, следовательно, coNP низок для PP - известны ли плохие последствия из этого? Если он находится в #P, то на самом деле coNP содержится в UP :), поэтому coNP = NP = UP = coUP.
Джошуа Грохов
Да, не уверен, но хороший вопрос.
Энди Друкер