56
$\begingroup$

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?

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

3 Answers 3

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Ashley Montanaro
    May 7, 2011 at 13:52
  • $\begingroup$ 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. $\endgroup$
    – Antonio Valerio Miceli-Barone
    May 8, 2011 at 15:04
  • 2
    $\begingroup$ @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. $\endgroup$
    – graffe
    May 9, 2011 at 13:40
  • $\begingroup$ @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}$ $\endgroup$
    – Antonio Valerio Miceli-Barone
    May 9, 2011 at 20:26
  • $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Apr 23, 2020 at 3:21
11
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ what's the main technique ? $\endgroup$
    – Suresh Venkat
    May 8, 2011 at 16:29
  • 2
    $\begingroup$ A short generating function. The following expository article would give us more ideas. arxiv.org/abs/math/0506466 $\endgroup$
    – Yoshio Okamoto
    May 9, 2011 at 0:24
  • $\begingroup$ The link is broken, and it is not saved on archive.org. Do you have a citation to the paper (title, authors, where published)? $\endgroup$
    – D.W.
    Jun 13 at 16:39
  • $\begingroup$ 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 $\endgroup$
    – Yoshio Okamoto
    Jun 14 at 17:37
11
$\begingroup$

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

2) Any set of affine signatures.

3) Non-negative weighted #CSPs

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.