Какова сложность подсчета числа решений задачи P-Space Complete? Как насчет классов повышенной сложности?

Я предполагаю, что это назвали бы # P-Space, но я нашел только одну статью, смутно упоминающую это. Как насчет подсчета версий EXP-TIME-Complete, NEXP-Complete, а также проблем EXP-SPACE-Complete? Есть ли какие-либо предыдущие работы, которые можно привести в отношении этого или любого типа включения или исключения, такие как теорема Тоды?

cc.complexity-theory complexity-classes counting-complexity pspace Тайфун Пей
источник

Вы задаете много вопросов в одном вопросе!

Цуёси Ито

#PSPACE - это то же самое, что и класс функций, которые могут быть вычислены в полиномиальном пространстве (FPSPACE).

Цуёси Ито

@ Tsuyoshi Это правда. Однако большинство вопросов, заданных, если не все, можно перефразировать как один общий вопрос: существуют ли классы подсчета для классов выше

(как можно заметить в определении #

) и применяются ли известные результаты?

N P

$NP$

P

$P$

chazisop

@Tayfun Pay: я не совсем уверен, что вы имеете в виду для таких детерминированных классов, как PSPACE, EXP, EXPSPACE. Понятие «количество решений» обычно тесно связано с недетерминизмом - с тех пор вы можете спросить о количестве принимаемых путей - или экзистенциальных квантификаторах / проекциях. В случае PSPACE, конечно, вы можете использовать определение чередующихся квантификаторов, но затем вам нужно указать, на какие квантификаторы вы хотите сосчитать, или тот факт, что NPSPACE = PSPACE.

Джошуа Грохов

Как уже упоминалось в нескольких комментариях, не совсем понятно, что вы хотели бы иметь в виду для #PSPACE. Лучше всего было бы взять дополненный аналог #L, который хорошо изучен. Поскольку #L содержится в DSPACE (log ^ 2 n), это будет означать, что # PSPACE = PSPACE, как @TsuyoshiIto, упомянутое выше. (Я игнорирую здесь нематериальное формальное различие между проблемами решения и функциями.)

Noam

Ответы:

-3

Число удовлетворяющих назначений для логической формулы равно количеству действительных количественных выражений формулы. Индуктивное доказательство довольно элегантно. Так что #P = #PSpace.

Даниэль Пехоушек
источник

Разве это не охватывается комментариями Цуёси и Ноама выше?

Гек Беннетт

\subseteq

$\subseteq$

^{# P}

$^{\#\mathrm{P}}$

@PeterShor Я вполне уверен, что Даниил имеет в виду этот mathoverflow.net/a/12608/35733 . Но мое (непроверенное) предположение состоит в том, что проблема с # PSPACE-завершением состоит в подсчете количества удовлетворяющих назначений фиксированного QBF, а не в подсчете количества выполнимых количественных определений данного CNF.

Сашо Николов

Нет, я имел в виду, что количество действительных количественных оценок данного cnf равно количеству удовлетворяющих присвоений cnf при фиксированном порядке переменных. Очень интересно, что изменение порядка переменных изменяет действительные значения qbfs, но не общее число допустимых значений qbfs.

Даниэль Пехоушек