Я читал статью в Википедии о проблеме восьми королев. Установлено, что не существует известной формулы для точного числа решений. После некоторых поисков я нашел статью под названием «О сложности подсчета проблем полных отображений». В этой статье есть проблема, показанная не более, чем #queens, которая выходит за пределы #P. Если взглянуть на числа #queens, которые в статье в Википедии исчерпывающе подсчитаны, они кажутся в значительной степени супер экспоненциальными.
Я хочу спросить, есть ли имя для этого класса или вообще есть ли проблемы с подсчетом, принадлежащие классам выше #P (с решением не в PSPACE, конечно, потому что это было бы очевидно).
Наконец, я хочу спросить, есть ли какие-либо другие известные результаты для других проблем поиска, таких как, например, нахождение трехцветной точки в лемме Спернера (PPAD complete).
Ответы:
Если функция f находится в #P, то при заданной входной строке x некоторой длины N значение f (x) является неотрицательным числом, ограниченным . (Это следует из определения с точки зрения количества принимающих путей верификатора NP.)2poly(N)
Это означает , что многие функции F лежат вне #P для неинтересных причин --- либо потому , что е является отрицательным, или, в случае , если вы упоминаете, потому что функция растет быстрее , чем . Но для проблемы n- kens, смоделированной в статье, это всего лишь артефакт решения авторов о том, что входное значение n должно быть закодировано в двоичном виде. Если ожидаемым вводом была одинарная строка 1 n , то2poly(N) n n 1n (число действительных nf(1n):= n -queen конфигурации), безусловно, будет в #P, с помощью простого верификатора NP, который проверяет правильность данной конфигурации.
Если вы хотите изучить некоторые функции, которые (предположительно) лежат за пределами #P по более интересным причинам, рассмотрите, например, эти:
Вам может не понравиться этот пример, потому что это не естественная «проблема подсчета». Но следующие два будут:
количество назначений для x, такое, что булева формула ψ ( x , ⋅ ) выполнима для некоторого значения y .f(ψ(x,y)):= x ψ(x,⋅) y
число x такое, что, по крайней мере, для половины всех y , ψ ( xf(ψ(x,y)):= x y .ψ(x,y)=1
Последние две проблемы, как известно, не являются эффективно вычисляемыми даже при доступе оракула к #P. Тем не менее, они вычислимы в рамках так называемой «иерархии подсчета». Для некоторых более естественных проблем, классифицированных в этом классе, см., Например, эту недавнюю статью.
Подсчет равновесий по Нэшу, по-видимому, очень сложен, смотрите здесь . Кроме того, даже проблемы, в которых проблема поиска проста, трудно подсчитать, например, подсчет идеальных совпадений.
источник
Сложность моделей подсчета линейной временной темпоральной логики Хазема Торфа, Мартина Циммермана
источник