14
$\begingroup$

I was reading the wikipedia article about the eight queens problem. It is stated that, there is no known formula for the exact number of solutions. After some searching, I found a paper named "On the hardness of counting problems of complete mappings". In this paper there is a problem, shown to be at most as hard as #queens, which is beyond #P. Getting a glimpse at the numbers of the #queens counted exhaustively in the wikipedia article, they seem pretty much super exponential.

I want to ask, if there is a name for this class or if in general there are counting problems belonging to classes above #P (with decision not in PSPACE of course because it would be obvious).

Finally, I want to ask if there are any other known results for other search problems, like finding a three-colored point in Sperner's Lemma for example (PPAD complete).

$\endgroup$
1

2 Answers 2

14
$\begingroup$

If the function f is in #P, then given an input string x of some length N, the value f(x) is a nonnegative number bounded by $2^{poly(N)}$. (This follows from the definition, in terms of number of accepting paths of an NP verifier.)

This means that many functions f lie outside of #P for uninteresting reasons---either because f is negative, or, in the case you mention, because the function grows faster than $2^{poly(N)}$. But for the $n$-queens problem as modeled in the paper, this is just an artifact of the authors' decision to let the input value $n$ be encoded in binary. If the expected input was the unary string $1^n$, then $f(1^n) :=$ (number of valid $n$-queen configurations) would certainly be in #P, by a simple NP verifier that checks validity of a given configuration.

If you want to explore some functions that (conjecturally) lie outside of #P for more interesting reasons, consider e.g. these:

  • UNSAT: $f(\psi) := 1$ if $\psi$ is an unsatisfiable Boolean formula, otherwise $f(\psi) := 0$. This function is not in #P, unless NP = coNP. It is probably not in the more general counting class GapP, either; that is, UNSAT is probably not the difference f - g of two #P functions. However, it lies in the more general counting complexity class $P^{\# P}$, which in fact contains the entire Polynomial Hierarchy by Toda's theorem.

You might not like that example because it is not a natural "counting problem". But the next two will be:

  • $f(\psi(x, y)) :=$ the number of assignments to $x$ such that the Boolean formula $\psi(x, \cdot)$ is satisfiable for some setting to $y$.

  • $f(\psi(x, y)) :=$ the number of $x$ such that, for at least half of all $y$, $\psi(x, y) = 1$.

The latter two problems are not known to be efficiently computable even with oracle access to #P. However, they are computable within the so-called "counting hierarchy". For some more natural problems classified within this class, see e.g. this recent paper.

Counting Nash equilibria is apparently #P-hard, see here. Also, even problems where the search problem is easy can be #P hard to count, e.g. counting perfect matchings.

$\endgroup$
2
  • 1
    $\begingroup$ For your UNSAT example, if it's in GapP, you get that coNP is in SPP, and hence coNP is low for PP - are bad consequences known to follow from this? If it's in #P then in fact coNP is contained in UP :), so coNP=NP=UP=coUP. $\endgroup$ Mar 17, 2015 at 17:31
  • $\begingroup$ Yeah, not sure but good question. $\endgroup$ Mar 17, 2015 at 23:41
3
$\begingroup$

In addition to the accepted answer, here is a recent paper (December '14) on the complexity of counting certain restricted models of Linear-time Temporal Logic. Higher, and more esoteric, complexity classes are present in the results shown: variants of the problem are $\#PSPACE$-complete, $\#EXPTIME$-complete, etc.

The Complexity of Counting Models of Linear-time Temporal Logic by Hazem Torfah, Martin Zimmermann

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.