# Above #P and counting search problems

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).

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.

• 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. – Joshua Grochow Mar 17 '15 at 17:31
• Yeah, not sure but good question. – Andy Drucker Mar 17 '15 at 23:41

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