<p>One interesting example from number theory is expressing a positive integer as a sum of four squares.  This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at <a href="https://dx.doi.org/10.1002%2Fcpa.3160390713">https://dx.doi.org/10.1002%2Fcpa.3160390713</a>), and if I remember correctly, there is now even a deterministic polynomial-time solution.  But counting the number of such representations would allow you to compute the sum-of-divisors function $\sigma(n)$, which is random polynomial-time equivalent to factoring $n$. So the counting problem is probably hard.</p>

CC BY-SA 3.0
2016-10-20T10:41:41.390Z
"So the counting problem is probably hard" you mean probably $\#P$ hard? do you have evidence?
Turbo
CC BY-SA 3.0
2016-10-20T14:02:44.097Z
By "probably hard" I mean it is random polynomial-time equivalent to integer factorization.
Jeffrey Shallit
CC BY-SA 3.0
2016-10-20T15:34:19.737Z
So, to make it explicit: the problem is *not* #P-hard (unless all hell breaks loose).
Emil Jeřábek
CC BY-SA 3.0
2016-10-21T14:46:59.463Z
@JeffreyShallit Is there a $\#P$ example?
Turbo
CC BY-SA 3.0
2017-02-23T03:38:19.437Z
I think the following is an even simpler example: "Does $n$ have a proper divisor greater than $1$" vs. "How many proper divisors greater than $1$ does $n$ have?".  The decision version is equivalent to "$n$ is composite" so it's in $P$, but the counting version doesn't look any easier than factoring.
Dan Brumleve
CC BY-SA 3.0
2016-10-20T09:55:59.647Z
2016-10-20T09:55:59.647Z
Jeffrey Shallit
<p>A very nice and simple example from Graph Theory is counting the number of Eularian circuits in an undirected graph.</p>

<p>The decision version is easy (... and the <a href="https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg">Seven Bridges of Königsberg problem</a> has no solution :-)</p>

<p>The counting version is #P-hard: Graham R. Brightwell, Peter Winkler:
<a href="http://www.siam.org/meetings/analco05/papers/09grbrightwell.pdf">Counting Eulerian Circuits is #P-Complete</a>. ALENEX/ANALCO 2005: 259-262</p>

CC BY-SA 3.0
2016-10-22T22:53:25.457Z
@MarzioDeBiasi is Eulerian circuit decision in NC?
Turbo
CC BY-SA 3.0
2016-10-22T22:55:39.677Z
@AJ. You just need to compute the parity of the degree of each node and check they are all even. Seems definitely to be in NC.
Sasho Nikolov
CC BY-SA 3.0
2016-10-23T04:29:08.410Z
@SashoNikolov actually not sure how parity at every node can be checked in $O(\log^cn)$ on $n^k$ processors if $|V|=n$ and worst case degree is $\Omega(n)$? So decision version may not be in $\mathsf{NC^i}$ at any fixed $i\in\Bbb N$.
Turbo
CC BY-SA 3.0
2016-10-23T15:50:50.147Z
You can take the parity of $n$ bits using an $O(n^2)$ size *formula* or a linear size circuit of depth $O(\log n)$. So if your graph is given as an adjacency matrix, compute the parity of each row, negate, and take an AND. AND of $n$ bits can be done with a linear size formula, so overall, you get an $O(n^3)$ size Boolean *formula* and a $O(n^2)$ size Boolean circuit of depth $O(\log n)$ (over the AND-OR basis). So the problem is in fact in $\mathsf{NC}^1$.
Sasho Nikolov
CC BY-SA 3.0
2016-10-25T07:56:21.383Z
In fact, the problem is in $\mathrm{AC}^0[2]$.
Emil Jeřábek
CC BY-SA 3.0
2016-10-20T12:55:56.603Z
2016-10-20T12:55:56.603Z
Marzio De Biasi
<p>Concerning your second question, problems such as Monotone-2-SAT (deciding of the satisfiability of a CNF-formula having at most 2 positive literals by clause) is completely trivial (you just have to check if your formula is empty or not) but the counting problem is #P-hard. Even approximating the number of satisfying assignments of such formula is hard (see On the hardness of approximate reasoning, Dan Roth, Artificial Intelligence, 1996).</p>

CC BY-SA 3.0
2016-10-21T14:26:32.393Z
2016-10-21T14:26:32.393Z
holf
<p>From <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/annihilatingPoly.pdf" rel="nofollow">[Kayal, CCC 2009]</a>: <strong>Explicitly evaluating annihilating polynomials at some point</strong></p>

<p>From the abstract: <em>``This is the only natural computational problem where
determining the existence of an object (the annihilating polynomial in our case) can be done efficiently but the actual computation of the object is provably hard.''</em></p>

<p>Let $\mathbb{F}$ be a field and $\vec{f} = (f_1, ..., f_k)\in\mathbb{F}[x_1, ..., x_n]$ be a set of $k$-many degree-$d$ $n$-variate polynomials over $\mathbb{F}.$ An <em>$\vec{f}$-annihilating polynomial</em> is any (non-trivial) $A$ s.t. $A(f_1, ..., f_k) = 0.$</p>

<p><em>Decision is easy:</em>
Over any field, and for any $k$ polynomials $(f_1, ..., f_k)$ -- if $k \ge n+1,$ there is such annihilating $A$ for $(f_1, ..., f_k)$. ((Via a dimension-counting argument.))</p>

<p><em>Counting is hard:</em> Define <strong>ANNIHILATING-EVAL</strong> as the functional problem of evaluating an annihilating polynomial on some point <strong>:</strong> Given a prime $p,$ and a set $(f_1, ..., f_k)\in\mathbb{Z}[x_1, ..., x_n]$ that have minimal monic annihilating $A(t_1, ..., t_k)\in\mathbb{Z}[t_1, ..., t_k],$ output the integer $A(0, ..., 0)\bmod{p}.$</p>

<p><strong>ANNIHILATING-EVAL</strong> is $\#\mathsf{P}$-hard. Moreover, the annihilating polynomial $A(t_1, ..., t_k)$ does not have a small circuit representation unless $\mathsf{PH}$ collapses.</p>

CC BY-SA 3.0
2016-10-21T15:13:48.910Z
The "simple way" to understand this (as the question asks) is that an annihilating polynomial existing is equivalent to a solution of a system of polynomial equations existing (whenever the system is over-determined). It's an algebraic version of what Gaussian Elimination does for systems of linear equations.
Daniel Apon
CC BY-SA 3.0
2016-10-22T14:12:38.580Z
@RickyDemer Ahh -- I may be outside of my particular expertise here. :) Can you point me to an example (URL?) of the difference in reduction that you're referring/care about for this question?
Daniel Apon
CC BY-SA 3.0
2016-10-22T14:56:11.653Z
(For my own curiosity =) )
Daniel Apon
CC BY-SA 3.0
2016-10-26T23:13:08.757Z
More generally, i.e. for arbitrary $k$ (even less than $n$), decision is easy because of the Jacobian criterion, right? (Note that the Jacobian criterion only works in characteristic > $max deg f_i$; in small positive characteristic, there is a modified Jacobian criterion due to [Mittman-Saxena-Scheiblechner](https://arxiv.org/abs/1202.4301), but that apparently only leads to an $\mathsf{NP}^{\mathsf{\# P}}$ algorithm for decision...)
Joshua Grochow
CC BY-SA 3.0
2016-10-21T15:02:12.933Z
2016-10-22T22:38:25.980Z
2016-10-22T22:38:25.980Z
Daniel Apon
<p>Here's a truly excellent example (I may be biased).  <br><br>
Given a partially ordered set:<br>
a) does it have a linear extension (i.e., a total order compatible with the partial order)? Trivial: All posets have at least one linear extension<br>
b) How many does it have?  #P-complete to determine this (Brightwell and Winkler, <a href="http://link.springer.com/article/10.1007/BF00383444">Counting Linear Extensions</a>, Order, 1991) <br>
c) Can we generate them all quickly? Yes, in constant amortized time (Pruesse and Ruskey, <a href="http://dx.doi.org/10.1137/S0097539791202647">Generating Linear Extensions Fast</a>, SIAM J Comp 1994)</p>

CC BY-SA 3.0
2016-10-26T22:59:49.960Z
+1: I agree it's a truly excellent example (was thinking of posting it myself and then saw this answer). Also, lest someone say "What about deciding if there's at least one *other* linear extension", that problem is also completely trivial: a total order has 1 extension, all other posets have > 1. And detecting exactly 2 extension is also easy (this happens iff there is exactly one pair of incomparable elements). In fact, there is a complete classification of posets with up to 7 linear extensions (see [Hanamura-Iwata, IPL 2011](http://dx.doi.org/10.1016/j.ipl.2011.01.004)).
Joshua Grochow
CC BY-SA 3.0
2016-10-27T10:13:41.963Z
This is a nice example indeed. There a much "simpler" problem however enjoying the same kind of properties (simpler in the sense that these properties are almost trivial to prove). Counting the number of satisfying assignments of a DNF: 
a) every non-empty DNF is satisfiable
b) counting is #P-complete (reduction to #SAT)
c) enumeration can be done with polynomial delay (an maybe constant amortized time, have to think about it)
holf
CC BY-SA 3.0
2016-11-01T16:50:57.970Z
I would be very interested in knowing if DNF satisfying assignments can be generated in constant amortized time (CAT).  At the time and my paper with Frank, in 1994, linear extensions were the first "naturally defined" object for which counting was hard and generation was as fast as it gets, when amortized (i.e., CAT).  DNF solutions seems like a likely candidate for this as well.  Does anyone have a reference?
Gara Pruesse
CC BY-SA 3.0
2016-11-02T08:58:49.350Z
@GaraPruesse I don't have references for that. For monotone-DNF, it is equivalent to enumerating hitting set of hypergraphs and some techniques for improving the delay are presented in "Efficient algorithms for dualizing large-scale hypergraphs" by Keisuke Murakami and Takeaki Uno http://dl.acm.org/citation.cfm?id=2611867. We should check if it gives CAT. For DNF, my intuition is that if there is a small clause then you already have enough solutions for brute forcing. Otherwise, you only have large clauses and which are then more likely to clash and that may be used to design a CAT algorithm.
holf
CC BY-SA 3.0
2016-10-26T18:23:32.163Z
2016-10-26T18:23:32.163Z
Gara Pruesse
<p><a href="https://en.wikipedia.org/wiki/Sharp-P-complete#Easy_problems_with_hard_counting_versions">Wikipedia</a> provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-SAT and number of topological sortings.</p>

<blockquote>
  <p>Are there any other important classes (say examples in lattices, trees, number theory and so on)? Is there a compendium of such problems?</p>
</blockquote>

<p>There are many types of problems in $P$ which have $\#P$-hard counting versions. </p>

<blockquote>
  <p>Is there a version of a natural problem in $P$ that is more completely understood  or simpler than general bipartite perfect matching (please include details on why simpler such as being <em>provably</em> in the lowest classes of the $NC$-hierarchy and so on) in some other area (such as number theory, lattices) or at least for particular simple bipartite graphs, whose counting version is $\#P$-hard?</p>
</blockquote>

<p><em>Examples from lattices, polytopes, point counting, number theory will be appreciated</em>.</p>

CC BY-SA 3.0
2016-10-20T03:33:05.807Z
@RickyDemer your writing is succinct. Yes I want natural problems.
Turbo
CC BY-SA 3.0
2016-10-21T19:38:33.647Z
Do we really not completely understand perfect matchings in bipartite graphs? Also, there is an RNC2 algorithm for the problem.
Sasho Nikolov
CC BY-SA 3.0
2016-10-21T19:44:33.050Z
Yes we do not. We do not have a deterministic $NC$ algorithm.
Turbo
<reference-request><counting-complexity><nt.number-theory><permanent><decision-trees>
Easy problems with hard counting versions
Turbo
# Easy problems with hard counting versions

(Asked by: username_0 on 2016-10-19)

[Wikipedia](https://en.wikipedia.org/wiki/Sharp-P-complete#Easy_problems_with_hard_counting_versions) provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-SAT and number of topological sortings.

> Are there any other important classes (say examples in lattices, trees, number theory and so on)? Is there a compendium of such problems?

There are many types of problems in $P$ which have $\#P$-hard counting versions.

> Is there a version of a natural problem in $P$ that is more completely understood or simpler than general bipartite perfect matching (please include details on why simpler such as being *provably* in the lowest classes of the $NC$-hierarchy and so on) in some other area (such as number theory, lattices) or at least for particular simple bipartite graphs, whose counting version is $\#P$-hard?

*Examples from lattices, polytopes, point counting, number theory will be appreciated*.

**Tags:** reference-request, counting-complexity, nt.number-theory, permanent, decision-trees

> **Comments:**
> **username_0**: @RickyDemer your writing is succinct. Yes I want natural problems.  
> **username_1**: Do we really not completely understand perfect matchings in bipartite graphs? Also, there is an RNC2 algorithm for the problem.  
> **username_0**: Yes we do not. We do not have a deterministic $NC$ algorithm.  

---

## 5 answers

### Answer by username_9 on 2016-10-26. Score: 9 | Accepted answer

Here's a truly excellent example (I may be biased).   
  
Given a partially ordered set:  
a) does it have a linear extension (i.e., a total order compatible with the partial order)? Trivial: All posets have at least one linear extension  
b) How many does it have? #P-complete to determine this (Brightwell and Winkler, [Counting Linear Extensions](http://link.springer.com/article/10.1007/BF00383444), Order, 1991)   
c) Can we generate them all quickly? Yes, in constant amortized time (Pruesse and Ruskey, [Generating Linear Extensions Fast](http://dx.doi.org/10.1137/S0097539791202647), SIAM J Comp 1994)

> **Comments:**
> **username_8**: +1: I agree it's a truly excellent example (was thinking of posting it myself and then saw this answer). Also, lest someone say "What about deciding if there's at least one *other* linear extension", that problem is also completely trivial: a total order has 1 extension, all other posets have > 1. And detecting exactly 2 extension is also easy (this happens iff there is exactly one pair of incomparable elements). In fact, there is a complete classification of posets with up to 7 linear extensions (see [Hanamura-Iwata, IPL 2011](http://dx.doi.org/10.1016/j.ipl.2011.01.004)).  
> **username_6**: This is a nice example indeed. There a much "simpler" problem however enjoying the same kind of properties (simpler in the sense that these properties are almost trivial to prove). Counting the number of satisfying assignments of a DNF:  a) every non-empty DNF is satisfiable b) counting is #P-complete (reduction to #SAT) c) enumeration can be done with polynomial delay (an maybe constant amortized time, have to think about it)  
> **username_9**: I would be very interested in knowing if DNF satisfying assignments can be generated in constant amortized time (CAT).  At the time and my paper with Frank, in 1994, linear extensions were the first "naturally defined" object for which counting was hard and generation was as fast as it gets, when amortized (i.e., CAT).  DNF solutions seems like a likely candidate for this as well.  Does anyone have a reference?  
> **username_6**: @GaraPruesse I don't have references for that. For monotone-DNF, it is equivalent to enumerating hitting set of hypergraphs and some techniques for improving the delay are presented in "Efficient algorithms for dualizing large-scale hypergraphs" by Keisuke Murakami and Takeaki Uno http://dl.acm.org/citation.cfm?id=2611867. We should check if it gives CAT. For DNF, my intuition is that if there is a small clause then you already have enough solutions for brute forcing. Otherwise, you only have large clauses and which are then more likely to clash and that may be used to design a CAT algorithm.  

---

### Answer by username_2 on 2016-10-20. Score: 17

One interesting example from number theory is expressing a positive integer as a sum of four squares. This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at <https://dx.doi.org/10.1002%2Fcpa.3160390713>), and if I remember correctly, there is now even a deterministic polynomial-time solution. But counting the number of such representations would allow you to compute the sum-of-divisors function $\sigma(n)$, which is random polynomial-time equivalent to factoring $n$. So the counting problem is probably hard.

> **Comments:**
> **username_0**: "So the counting problem is probably hard" you mean probably $\#P$ hard? do you have evidence?  
> **username_2**: By "probably hard" I mean it is random polynomial-time equivalent to integer factorization.  
> **username_3**: So, to make it explicit: the problem is *not* #P-hard (unless all hell breaks loose).  
> **username_0**: @JeffreyShallit Is there a $\#P$ example?  
> **username_4**: I think the following is an even simpler example: "Does $n$ have a proper divisor greater than $1$" vs. "How many proper divisors greater than $1$ does $n$ have?".  The decision version is equivalent to "$n$ is composite" so it's in $P$, but the counting version doesn't look any easier than factoring.  

---

### Answer by username_5 on 2016-10-20. Score: 17

A very nice and simple example from Graph Theory is counting the number of Eularian circuits in an undirected graph.

The decision version is easy (... and the [Seven Bridges of Königsberg problem](https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg) has no solution :-)

The counting version is #P-hard: Graham R. Brightwell, Peter Winkler:
[Counting Eulerian Circuits is #P-Complete](http://www.siam.org/meetings/analco05/papers/09grbrightwell.pdf). ALENEX/ANALCO 2005: 259-262

> **Comments:**
> **username_0**: @MarzioDeBiasi is Eulerian circuit decision in NC?  
> **username_1**: @AJ. You just need to compute the parity of the degree of each node and check they are all even. Seems definitely to be in NC.  
> **username_0**: @SashoNikolov actually not sure how parity at every node can be checked in $O(\log^cn)$ on $n^k$ processors if $|V|=n$ and worst case degree is $\Omega(n)$? So decision version may not be in $\mathsf{NC^i}$ at any fixed $i\in\Bbb N$.  
> **username_1**: You can take the parity of $n$ bits using an $O(n^2)$ size *formula* or a linear size circuit of depth $O(\log n)$. So if your graph is given as an adjacency matrix, compute the parity of each row, negate, and take an AND. AND of $n$ bits can be done with a linear size formula, so overall, you get an $O(n^3)$ size Boolean *formula* and a $O(n^2)$ size Boolean circuit of depth $O(\log n)$ (over the AND-OR basis). So the problem is in fact in $\mathsf{NC}^1$.  
> **username_3**: In fact, the problem is in $\mathrm{AC}^0[2]$.  

---

### Answer by username_6 on 2016-10-21. Score: 6

Concerning your second question, problems such as Monotone-2-SAT (deciding of the satisfiability of a CNF-formula having at most 2 positive literals by clause) is completely trivial (you just have to check if your formula is empty or not) but the counting problem is #P-hard. Even approximating the number of satisfying assignments of such formula is hard (see On the hardness of approximate reasoning, Dan Roth, Artificial Intelligence, 1996).


---

### Answer by username_7 on 2016-10-21. Score: 5

From [[Kayal, CCC 2009]](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/annihilatingPoly.pdf): **Explicitly evaluating annihilating polynomials at some point**

From the abstract: *``This is the only natural computational problem where
determining the existence of an object (the annihilating polynomial in our case) can be done efficiently but the actual computation of the object is provably hard.''*

Let $\mathbb{F}$ be a field and $\vec{f} = (f\_1, ..., f\_k)\in\mathbb{F}[x\_1, ..., x\_n]$ be a set of $k$-many degree-$d$ $n$-variate polynomials over $\mathbb{F}.$ An *$\vec{f}$-annihilating polynomial* is any (non-trivial) $A$ s.t. $A(f\_1, ..., f\_k) = 0.$

*Decision is easy:*
Over any field, and for any $k$ polynomials $(f\_1, ..., f\_k)$ -- if $k \ge n+1,$ there is such annihilating $A$ for $(f\_1, ..., f\_k)$. ((Via a dimension-counting argument.))

*Counting is hard:* Define **ANNIHILATING-EVAL** as the functional problem of evaluating an annihilating polynomial on some point **:** Given a prime $p,$ and a set $(f\_1, ..., f\_k)\in\mathbb{Z}[x\_1, ..., x\_n]$ that have minimal monic annihilating $A(t\_1, ..., t\_k)\in\mathbb{Z}[t\_1, ..., t\_k],$ output the integer $A(0, ..., 0)\bmod{p}.$

**ANNIHILATING-EVAL** is $\#\mathsf{P}$-hard. Moreover, the annihilating polynomial $A(t\_1, ..., t\_k)$ does not have a small circuit representation unless $\mathsf{PH}$ collapses.

> **Comments:**
> **username_7**: The "simple way" to understand this (as the question asks) is that an annihilating polynomial existing is equivalent to a solution of a system of polynomial equations existing (whenever the system is over-determined). It's an algebraic version of what Gaussian Elimination does for systems of linear equations.  
> **username_7**: @RickyDemer Ahh -- I may be outside of my particular expertise here. :) Can you point me to an example (URL?) of the difference in reduction that you're referring/care about for this question?  
> **username_7**: (For my own curiosity =) )  
> **username_8**: More generally, i.e. for arbitrary $k$ (even less than $n$), decision is easy because of the Jacobian criterion, right? (Note that the Jacobian criterion only works in characteristic > $max deg f_i$; in small positive characteristic, there is a modified Jacobian criterion due to [Mittman-Saxena-Scheiblechner](https://arxiv.org/abs/1202.4301), but that apparently only leads to an $\mathsf{NP}^{\mathsf{\# P}}$ algorithm for decision...)  

---

