# Surprising algorithms for counting problems

There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples include:

A key step in both of these examples is reducing the counting problem to computing the determinant of a certain matrix. A determinant is itself, of course, a sum of exponentially many things, yet can surprisingly be computed in polynomial time.

My question is: are there any "surprisingly efficient" exact and deterministic algorithms known for counting problems which do not reduce to computing a determinant?

• BTW, many more counting problems reduce to computing the determinant. Integer determinant is complete for the class GapL, which contains #L.
– 5501
May 5, 2011 at 8:52

I don't know if the following problems reduce or not to computing the determinant, but I will list anyway:

1) Counting the number of paths in a DAG from a node $v_0$ to a node $v_f$. But this is not surprising. Simply determining whether $v_f$ is reachable from $v_0$ is in NL, and thus in DET. I have no idea about the counting version.

2) Counting the number of solutions of problems definable in MSO-logic in structures of bounded Tree width. See for example the paper which buids on works of Courcelle, Arnborg and others.

3) If you have a function $f:\{0,1\}^{n}\rightarrow \{0,1\}$, that can be expressed by a bolean circuit of logarithmic tree width, than you can count the number of inputs $x$ such that $f(x)=1$ by devising a quantum circuit $U_f$ which sends $|x\rangle|0\rangle$ to $|x\rangle|f(x)\rangle$, and classically simulating the probability of measuring $|1\rangle$ in the second register after the application of $U_fH^{\otimes n}|0\rangle|0\rangle$ using these results.

• Thanks - items (2) and (3) are interesting but somehow not quite what I was looking for; counting problems with bounded tree-width seem more like special cases where the structure you are working with is actually polynomially bounded. I was more interested in cases where there are "really" exponentially many objects to count, but they can somehow magically be counted in polynomial time. May 7, 2011 at 13:52
• Wouldn't that mean that, if you use an unary encoding, the algorithm needs exponential time just to write the number? Is it possible that this problem is overcome by using binary encoding, but this sounds conterintuitive to me. May 8, 2011 at 15:04
• @Miceli-Barone, What you say would apply to pretty much any poly time algorithm that outputs a number. The determinant itself would be rather large in the worst case in unary.
– Simd
May 9, 2011 at 13:40
• @Raphael: ok, I see that the absolute value of determinant of a (0,1)-matrix is bounded by $\frac{(n + 1)^{\frac{n+1}{2}}}{2^n}$ May 9, 2011 at 20:26
• Counting paths in a DAG can be done in poly time by simple dynamic programming. DP is also a very standard method for many problems on graphs of bounded treewidth. Apr 23, 2020 at 3:21

Counting the number of lattice points in a rational polytope (when the dimension is constant) in polynomial time, due to Alexander Barvinok.

• what's the main technique ? May 8, 2011 at 16:29
• A short generating function. The following expository article would give us more ideas. arxiv.org/abs/math/0506466 May 9, 2011 at 0:24
• The link is broken, and it is not saved on archive.org. Do you have a citation to the paper (title, authors, where published)?
– D.W.
Jun 13, 2022 at 16:39
• Alexander I. Barvinok: A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed. Math. Oper. Res. 19(4): 769-779 (1994) doi.org/10.1287/moor.19.4.769 Jun 14, 2022 at 17:37

In the Holant framework, there are several cases that are tractable (for non-trivial) reasons other than via matchgates in planar graphs.

2) Any set of affine signatures.

...to name a few.

Also, the BEST Theorem gives a polynomial time algorithm for counting the number of Eulerian circuits in a directed graph, though part of the algorithm does use a determinant calculation.