<p>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.</p>

<p><a href="http://arxiv.org/abs/1408.5752" rel="nofollow">The Complexity of Counting Models of Linear-time Temporal Logic</a> by Hazem Torfah, Martin Zimmermann</p>

CC BY-SA 3.0
2015-03-12T19:50:33.447Z
2015-03-12T19:50:33.447Z
alakh
<p>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.)</p>

<p>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.</p>

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

<ul>
<li>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.</li>
</ul>

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

<ul>
<li><p>$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$.</p></li>
<li><p>$f(\psi(x, y)) :=$ the number of $x$ such that, for at least half of all $y$, $\psi(x, y) = 1$.</p></li>
</ul>

<p>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. <a href="http://www.lix.polytechnique.fr/~mengel/papers/monomialsSTACS12.pdf">this</a> recent paper.</p>

<p>Counting Nash equilibria is apparently #P-hard, see <a href="http://arxiv.org/abs/cs/0205074">here</a>.  Also, even problems where the search problem is easy can be #P hard to count, e.g. counting perfect matchings.</p>

CC BY-SA 3.0
2015-03-17T17:31:47.400Z
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
CC BY-SA 3.0
2015-03-17T23:41:24.553Z
Yeah, not sure but good question.
Andy Drucker
CC BY-SA 3.0
2015-03-10T10:09:51.747Z
2015-03-10T10:09:51.747Z
Andy Drucker
<p>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. </p>

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

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

CC BY-SA 3.0
2015-03-10T08:40:46.800Z
Might be helpful: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.989
Markus Bläser
<cc.complexity-theory><counting-complexity><search-problem>
Above #P and counting search problems
Paramar
# Above #P and counting search problems

(Asked by: username_0 on 2015-03-09)

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

**Tags:** cc.complexity-theory, counting-complexity, search-problem
> **Comments:**
> **username_1**: Might be helpful: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.989  

---

## 2 answers

### Answer by username_3 on 2015-03-10. Score: 14 | Accepted answer

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](http://www.lix.polytechnique.fr/~mengel/papers/monomialsSTACS12.pdf) recent paper.

Counting Nash equilibria is apparently #P-hard, see [here](http://arxiv.org/abs/cs/0205074). Also, even problems where the search problem is easy can be #P hard to count, e.g. counting perfect matchings.

> **Comments:**
> **username_4**: 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.  
> **username_3**: Yeah, not sure but good question.  

---

### Answer by username_2 on 2015-03-12. Score: 3

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](http://arxiv.org/abs/1408.5752) by Hazem Torfah, Martin Zimmermann


---

