22
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Presumably you want natural problems, since [by reduction from #SAT, problems that #P-hard under [reductions that multiply answer by a non-zero number] have HP-hard decision problems] and [by the identity function, {x : x is 1+(number_of_variables_($\phi$)) ones or [a zero followed by a satisfying assignment to $\phi$]} is #P-hard under the next-most-strict type of reduction, but its decision version is trivial]. ​ ​ $\endgroup$
    – user6973
    Oct 20, 2016 at 2:52
  • $\begingroup$ @RickyDemer your writing is succinct. Yes I want natural problems. $\endgroup$
    – Turbo
    Oct 20, 2016 at 3:33
  • $\begingroup$ Do we really not completely understand perfect matchings in bipartite graphs? Also, there is an RNC2 algorithm for the problem. $\endgroup$
    – Sasho Nikolov
    Oct 21, 2016 at 19:38
  • 1
    $\begingroup$ Yes we do not. We do not have a deterministic $NC$ algorithm. $\endgroup$
    – Turbo
    Oct 21, 2016 at 19:44

5 Answers 5

Reset to default
9
$\begingroup$

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, Order, 1991)
c) Can we generate them all quickly? Yes, in constant amortized time (Pruesse and Ruskey, Generating Linear Extensions Fast, SIAM J Comp 1994)

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ +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). $\endgroup$
    – Joshua Grochow
    Oct 26, 2016 at 22:59
  • $\begingroup$ 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) $\endgroup$
    – holf
    Oct 27, 2016 at 10:13
  • $\begingroup$ 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? $\endgroup$
    – Gara Pruesse
    Nov 1, 2016 at 16:50
  • $\begingroup$ @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 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. $\endgroup$
    – holf
    Nov 2, 2016 at 8:58
17
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ "So the counting problem is probably hard" you mean probably $\#P$ hard? do you have evidence? $\endgroup$
    – Turbo
    Oct 20, 2016 at 10:41
  • $\begingroup$ By "probably hard" I mean it is random polynomial-time equivalent to integer factorization. $\endgroup$
    – Jeffrey Shallit
    Oct 20, 2016 at 14:02
  • 3
    $\begingroup$ So, to make it explicit: the problem is not #P-hard (unless all hell breaks loose). $\endgroup$
    – Emil Jeřábek
    Oct 20, 2016 at 15:34
  • $\begingroup$ @JeffreyShallit Is there a $\#P$ example? $\endgroup$
    – Turbo
    Oct 21, 2016 at 14:46
  • $\begingroup$ 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. $\endgroup$
    – Dan Brumleve
    Feb 23, 2017 at 3:38
17
$\begingroup$

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 has no solution :-)

The counting version is #P-hard: Graham R. Brightwell, Peter Winkler: Counting Eulerian Circuits is #P-Complete. ALENEX/ANALCO 2005: 259-262

Improve this answer
$\endgroup$
6
  • $\begingroup$ That paper's ​ ​ ​ "Our approach is to show that, with the help of an oracle which counts Eulerian circuits, a Turing machine can ... ​ ​ ​ and ​ ​ ​ "We wish to compute the number $N$ of Eulerian orientations of $G$." ​ paragraph-break ​ "We construct for any odd prime $p$, a graph $G_p$ whose number of orbs is equivalent to $N$ modulo $p$." ​ ​ ​ and ​ ​ ​ "We repeat this process for every prime p between $m$ and $m^2$, where $|E| = m$, and ..." ​ ​ ​ certainly suggest that they only give a parallel reduction, rather than even a $m^{\epsilon}$-query reduction. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Oct 21, 2016 at 8:32
  • $\begingroup$ @MarzioDeBiasi is Eulerian circuit decision in NC? $\endgroup$
    – Turbo
    Oct 22, 2016 at 22:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – Sasho Nikolov
    Oct 22, 2016 at 22:55
  • 4
    $\begingroup$ 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$. $\endgroup$
    – Sasho Nikolov
    Oct 23, 2016 at 15:50
  • 2
    $\begingroup$ In fact, the problem is in $\mathrm{AC}^0[2]$. $\endgroup$
    – Emil Jeřábek
    Oct 25, 2016 at 7:56
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

From [Kayal, CCC 2009]: 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.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Like for Marzio's example, that paper's proof of claim 15.2 seems to indicate that they only show hardness under parallel reductions, rather than even under $m^{\hspace{.02 in}\epsilon}$-query reductions. ​ ​ $\endgroup$
    – user6973
    Oct 22, 2016 at 0:32
  • 1
    $\begingroup$ The resources I can find all seem to disagree on the definitions. ​ ​ ​ ​ ​ ​ ​ Let AE be the problem your answer discusses. ​ (... continued) ​ ​ ​ ​ $\endgroup$
    – user6973
    Oct 23, 2016 at 7:33
  • 1
    $\begingroup$ (continued ...) ​ ​ ​ ​ ​ ​ ​ I haven't tried to work out more precisely what base-class they use, but would be quite surprised if their result was better than ​ ​ ​ #P ​ = ​ $\big(\hspace{-0.07 in}$ DLOGTIME-uniform TC$^0$ $\hspace{-0.06 in}\big)$ $^{\hspace{-0.06 in}||\hspace{-0.06 in}}$ $^{\text{AE}}$ $^{\hspace{-0.05 in}[\sqrt{n}]}$ ​ . ​ ​ ​ ​ ​ ​ ​ (... continued) ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Oct 23, 2016 at 7:33
  • 1
    $\begingroup$ (continued ...) ​ ​ ​ As far as I can see, it does not follow that ​ LWPP $\subseteq$ MP$^{\text{AE}}$$^{[\sqrt[3]{n}]}$$\hspace{-0.06 in}\big/\hspace{-0.04 in}$poly . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Oct 23, 2016 at 7:33
  • 1
    $\begingroup$ 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, but that apparently only leads to an $\mathsf{NP}^{\mathsf{\# P}}$ algorithm for decision...) $\endgroup$
    – Joshua Grochow
    Oct 26, 2016 at 23:13

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.