<p><a href="http://mor.journal.informs.org/cgi/content/abstract/19/4/769">Counting the number of lattice points in a rational polytope (when the dimension is constant) in polynomial time</a>, due to Alexander Barvinok.</p>

CC BY-SA 3.0
2011-05-08T16:29:39.093Z
what's the main technique ?
Suresh Venkat
CC BY-SA 3.0
2011-05-09T00:24:16.080Z
A short generating function. The following expository article would give us more ideas.  http://arxiv.org/abs/math/0506466
Yoshio Okamoto
CC BY-SA 4.0
2022-06-13T16:39:22.503Z
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.
CC BY-SA 4.0
2022-06-14T17:37:50.923Z
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) https://doi.org/10.1287/moor.19.4.769
Yoshio Okamoto
CC BY-SA 3.0
2011-05-08T13:38:20.227Z
2011-05-08T13:38:20.227Z
Yoshio Okamoto
<p>I don't know if the following problems reduce or not to computing the determinant, but I will list anyway:</p>

<p>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 <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aD#det">DET</a>. I have no idea about the counting version.</p>

<p>2) Counting the number of solutions of problems definable in MSO-logic in structures of bounded Tree width.  See for example <a href="http://www.dbai.tuwien.ac.at/proj/tractability/JaklPRW08b.pdf">the paper which buids on works of Courcelle, Arnborg and others</a>.</p>

<p>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$ <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.128.9165">using these results</a>.</p>

CC BY-SA 3.0
2011-05-07T13:52:48.703Z
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.
Ashley Montanaro
CC BY-SA 3.0
2011-05-08T15:04:45.260Z
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.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-05-09T13:40:52.360Z
@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
CC BY-SA 3.0
2011-05-09T20:26:04.987Z
@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}$
Antonio Valerio Miceli-Barone
CC BY-SA 4.0
2020-04-23T03:21:17.890Z
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.
Joshua Grochow
CC BY-SA 3.0
2011-05-04T21:34:48.563Z
2011-05-05T14:50:02.173Z
2011-05-05T14:50:02.173Z
Mateus de Oliveira Oliveira
<p>In the Holant framework, there are several cases that are tractable (for non-trivial) reasons other than via matchgates in planar graphs.</p>

<p>1) <a href="http://pages.cs.wisc.edu/~jyc/papers/fibonacci.pdf">Fibonacci Gates</a></p>

<p>2) Any set of <a href="http://pages.cs.wisc.edu/~jyc/papers/cw-csp.pdf">affine signatures</a>.</p>

<p>3) <a href="http://pages.cs.wisc.edu/~jyc/papers/weighted-CSP.pdf">Non-negative weighted #CSPs</a></p>

<p>...to name a few.</p>

<p>Also, the <a href="http://en.wikipedia.org/wiki/BEST_theorem">BEST Theorem</a> 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.</p>

CC BY-SA 3.0
2011-05-17T14:51:46.183Z
2011-05-17T15:06:24.873Z
2011-05-17T15:06:24.873Z
Tyson Williams
<p>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:</p>

<ul>
<li>Counting perfect matchings in a planar graph (the <a href="http://en.wikipedia.org/wiki/FKT_algorithm">FKT algorithm</a>), which is the basis for how <a href="http://en.wikipedia.org/wiki/Holographic_algorithm">holographic algorithms</a> work.
<li> Counting spanning trees in a graph (via <a href="http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem">Kirchhoff's matrix tree theorem</a>).
</ul>

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

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

CC BY-SA 3.0
2011-05-05T08:52:46.683Z
BTW, many more counting problems reduce to computing the determinant. Integer determinant is complete for the class GapL, which contains #L.
5501
<cc.complexity-theory><counting-complexity><big-picture>
Surprising algorithms for counting problems
Ashley Montanaro
# Surprising algorithms for counting problems

(Asked by: username_0 on 2011-05-04)

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:

* Counting perfect matchings in a planar graph (the [FKT algorithm](http://en.wikipedia.org/wiki/FKT_algorithm)), which is the basis for how [holographic algorithms](http://en.wikipedia.org/wiki/Holographic_algorithm) work.* Counting spanning trees in a graph (via [Kirchhoff's matrix tree theorem](http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem)).

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?

**Tags:** cc.complexity-theory, counting-complexity, big-picture

> **Comments:**
> **username_1**: BTW, many more counting problems reduce to computing the determinant. Integer determinant is complete for the class GapL, which contains #L.  

---

## 3 answers

### Answer by username_2 on 2011-05-08. Score: 11

[Counting the number of lattice points in a rational polytope (when the dimension is constant) in polynomial time](http://mor.journal.informs.org/cgi/content/abstract/19/4/769), due to Alexander Barvinok.

> **Comments:**
> **username_3**: what's the main technique ?  
> **username_2**: A short generating function. The following expository article would give us more ideas.  http://arxiv.org/abs/math/0506466  
> **username_4**: The link is broken, and it is not saved on archive.org.  Do you have a citation to the paper (title, authors, where published)?  
> **username_2**: 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) https://doi.org/10.1287/moor.19.4.769  

---

### Answer by username_5 on 2011-05-04. Score: 11

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](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aD#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](http://www.dbai.tuwien.ac.at/proj/tractability/JaklPRW08b.pdf).

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.128.9165).

> **Comments:**
> **username_0**: 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.  
> **username_6**: 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.  
> **username_7**: @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.  
> **username_6**: @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}$  
> **username_8**: 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.  

---

### Answer by username_9 on 2011-05-17. Score: 11

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

1) [Fibonacci Gates](http://pages.cs.wisc.edu/~jyc/papers/fibonacci.pdf)

2) Any set of [affine signatures](http://pages.cs.wisc.edu/~jyc/papers/cw-csp.pdf).

3) [Non-negative weighted #CSPs](http://pages.cs.wisc.edu/~jyc/papers/weighted-CSP.pdf)

...to name a few.

Also, the [BEST Theorem](http://en.wikipedia.org/wiki/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.


---

