On the complexity of counting exactly and approximately

Larry Stockmeyer was one of the great theorists, who worked on areas as diverse as lower bounds on logical theories, computational complexity, distributed computing, algorithms, and many other areas. He passed away in 2004, and is terribly missed by all who knew him. See Lance Fortnow’s wonderful tribute for many details on Larry’s contributions.

Today I want to talk about one of Larry’s great results: an approximate counting method. I have always loved this result.

Larry was quiet, but beneath his quiet exterior he had a tremendous sense of humor. He was also one of the most powerful problem solvers that I had ever had the pleasure to work with. Larry was also extremely accurate—if Larry said that X was true, you could bet the house that X was true. He was amazing at finding loose ends in an argument, and usually then finding a way to tie them up.

I once proved a result on the complexity of univariate polynomials, and I showed a draft of the paper to Larry. A few hours later he came into my office—I was visiting IBM Yorktown at the time—with my paper all marked up. Larry then started to give me very detailed comments about the substance of the paper. After a while I started to get nervous; I was starting to wonder whether or not the main result of my paper was correct or not. I finally asked Larry directly: “is the theorem correct?” He said,

“oh yes, but here you need to argue that ${\dots}$

I was quite relieved. Larry and I went on to work together on other results on the complexity of polynomials.

A year later, again at IBM Yorktown, we had two visitors George Sacerdote and Richard Tenney, who came to IBM and gave a very technical talk on their solution to the Vector Addition System (VAS) reachability problem. It was a long, almost two hour talk, that was attended by the most of the IBM theory group. The reachability problem had been claimed before, and I had worked hard on the problem in the past—with no success. So I was very interested to see if they had really solved the problem.

When the talk was over, we all started to leave the conference room and head to the IBM cafeteria for lunch. I stood right at the door and did an “exit poll”—as each theorist left the room I asked them what they thought about the proof. Did they believe it? Did it look like it might work? Most said that it sounded plausible. A few were even more positive: one member said that he was convinced that the proof would work. Personally, I thought that I had not heard anything new, but nor had I heard anything wrong. I was on the fence.

I then asked the last to exit the room, Larry, what he thought about the proof. Larry said,

“I did not understand a word that they said.”

Larry was right on the money. The proof was wrong, but it took a lot of work, by many people, to eventually find the holes in their attempted proof. See my post for more about the VAS problem.

Let’s turn to Larry’s result on approximate counting.

Approximate Counting

Suppose that ${C(x)}$ is a circuit with inputs ${x=x_{1},\dots,x_{n}}$ of size polynomial in ${n}$. Then, a natural question is: How many ${x}$ satisfy ${C(x)=1}$? This is well known to be a ${\#}$P complete problem, and computing the exact answer is certainly at least as hard as NP. What Larry looked is how hard is it to approximately determine the number of ${x}$ so that ${C(x)=1}$? Let ${S = \{x \mid C(x)=1\}}$.

A key observation is that there is an amplifier lurking here: if we can in general determine ${|S|}$ to within a factor of ${2}$ in polynomial time, then we can determine it to within factor ${1+\frac{1}{n^{c}}}$ for any constant ${c}$ also in polynomial time. This can be proved by a simple amplification argument. The idea is this: create a new circuit ${D(x,y) = C(x) \wedge C(y)}$ where ${x}$ and ${y}$ are disjoint inputs.

Then, ${D(x,y)}$ has ${|S|^{2}}$ inputs that it accepts. If you know ${|S|^{2}}$ to a factor of ${2}$, then you know ${|S|}$ to a factor of ${\sqrt 2}$. An ${m}$-fold version of this will yield a approximation of

$\displaystyle 2^{\frac{1}{m}} \approx 1 + O(\frac{1}{m}).$

I have just discussed amplifiers, and this is a perfect example of the power of even a simple repetition amplifier.

Thus, the key problem is to determine ${|S|}$ to within a factor of ${2}$. Larry proves,

Theorem: There is a random algorithm that determines ${|S|}$ to within a factor of ${2}$ in polynomial time provided it has access to an NP-oracle.

Note, there is no way to remove the need for the oracle, without a breakthrough, since it is easy to construct an NP-hard problem that either has no solutions or many solutions. Thus, determining the answer to within a factor of ${2}$ without the oracle would imply that P=NP.

Sketch of Larry’s proof

Larry’s proof uses some ideas that had been used earlier by Mike Sipser, but he added several additional insights. See his paper for the details, but I will give a quick overview of how the counting method works.

Let ${C(x)}$ be the circuit and let ${S}$ be the set of inputs ${x}$ so that ${C(x)=1}$. Suppose that our goal is really modest: we want to know if ${|S|}$ is really large, or really small. Take a random hash function ${h:\{0,1\}^{n} \rightarrow \{0,1\}^{m}}$ where ${m}$ is much smaller than ${n}$. Then, check to see if there are two distinct ${x}$ and ${y}$ so that they form a “collision”,

$\displaystyle h(x) = h(y), \ \ \ \ \ (1)$

and both are in ${S}$. If ${|S|}$ is small then, it is likely that (1) will have no solutions, but if ${|S|}$ is large, then (1) is likely to have solutions. The key to make this work is careful analysis of the probabilities of collisions for the given hash functions. This can be worked out to prove the theorem. Note, the detection of a collision requires an oracle call: “are there two distinct ${x}$ and ${y}$ such that ${h(x)=h(y)=1}$ and both are in ${S}$”?

Counting and Finite Automata

I love finite state automata (FSA)—as you probably know. The following theorem is not as well known as it should be, in my opinion at least:

Theorem: Suppose that ${M}$ is a ${m}$-state deterministic finite state automaton. Then, the number of length ${n}$ inputs that are accepted by ${M}$ can be computed exactly in polynomial time in ${n}$ and ${m}$.

Thus, for FSA, the problem of counting the number of accepting computations is easy.

A proof sketch is the following—unfortunately I cannot find a paper to point to here, any help would be appreciated. Perhaps its a folklore theorem, since I have known it forever. Let ${M'}$ be a new automata that simulates ${M}$ on all inputs of length ${n}$, and has the property that the state diagram is acyclic. Essentially, ${M'}$ replaces each state ${s}$ of ${M}$ by the state ${(s,i)}$ where ${i=0,\dots,n}$. For example, if ${a \rightarrow b}$ was a transition on input ${0}$, then

$\displaystyle (a,i) \rightarrow (b,i+1)$

is a transition for input ${0}$ for all ${i}$. We have simply unrolled the automaton ${M}$ to avoid any loops: this cannot be done in general, but is fine if we are only concerned with inputs of a fixed length ${n}$.

The algorithm then inductively labels each state ${(a,i)}$ with the number of length-${i}$ inputs that reach this state. To label a state ${(b,i+1)}$, we take each state ${(a,i)}$ with arcs to ${(b,i+1)}$, and add the number of ${(a,i)}$ times the number of arcs from ${a}$ to ${b}$. The number of accepting computations of length ${n}$ is then the sum of the numbers for ${(b,n)}$ with ${b}$ an accepting state of the original ${M}$.

Open Problems

Can we improve the result of Stockmeyer on approximate counting? For specific problems there are better results known of course, but I wonder can we improve his counting argument? Of course if P=NP, then approximate counting would be in polynomial time, but can it be in NP?

Ken Regan, who helped with this post, points out an interesting connection between Larry’s theorem and quantum computation—he promises to post a comment on it.

Another natural question that I think might be worth working on is this: pick a complexity class that could be weaker than polynomial time and see what the cost of approximate counting is for that class. I have given a simple example, above, where exact counting is easy. There is some quite nice work on approximate counting for certain simple classes of circuits—I will leave that for another day.

August 27, 2009 7:45 am

For the FSA counting, why not just compute the generating function (in constant time) and then use Taylor series or run the recursion?

2. August 27, 2009 1:21 pm

An interesting related question is to count the number of inputs of length n that an NFA with m states accepts. This is a #P-hard problem. However, one can obtain a (1+\eps) approximation in n^{O(log n/\eps)} time. This is in a paper of Gore etal which also shows how to count the number of strings of length n accepted by a context free grammar.
ftp://ftp.cis.upenn.edu/pub/kannan/newj.ps.gz

I think it is still an open problem to improve the quasi-polynomial time to a polynomial time.

August 27, 2009 1:25 pm

Thanks. I did not know this result. Thanks again for the pointer. Would be cool to improve the bound.

3. August 27, 2009 6:44 pm

Here’s the connection in brief. BQP is the feasible quantum computing class analogous to BPP, but unlike BPP it contains (the decision version of) factoring and other interesting stuff. Also unlike BPP, it is not known to be contained in the polynomial hierarchy.

You can reduce a BPP question to approximating a single #P function, but with BQP what you get is the difference of two #P functions, call them f and g. Approximating f and g separately does not help you approximate f – g when f – g is near zero!

BQP does give you a little help: When the answer to the BQP question on an input x is yes, you get that f(x) – g(x) is close to the square root of 2^m, where the counting predicates defining f and g have m binary variables after you substitute for x. (There are no absolute-value bars; “magically” you always get f(x) > g(x). Under common representations of quantum circuits for BQP, m becomes the number of Hadamard gates.) When the answer is no, the difference is close to 0. Doing Stockmeyer approximation on f and g separately still fails basically because 2^{m/2} is not a polynomial fraction of 2^m. The open question is what other counting and approximation tricks might come into play…

4. August 29, 2009 11:49 am

On “counting accepted n-length strings in an m-state DFA is in P”:
Yes, it is folklore.

Even better, the problem is in NC. In the class #L, of functions that report the number of accepting paths of a logspace-bounded machine, and hence expressible as the determinant of a related integer matrix. Why? Unroll the DFA into an acyclic graph on n-length inputs. Each node has out-degree 2. Now let an NLOG machine trace out a path in this graph, choosing an out-edge nondeterministically, and accepting if the final state reached is an accepting state.

I’m not sure what would be a good reference: I believe (courtesy Eric Allender) that the unrolling idea goes back to Neil Jones in the 1970s. Certainly, the idea has been used implicitly or explicitly in almost all papers dealing with #L or GapL.

Related result: instead of counting inputs, what if we just want to test if a particular input is accepted? ie Membership testing. If the NFA is also part of the input, this is NLOG-complete. (As opposed to when the NFA is fixed; this would be NC^1 complete. Also, as opposed to when the NFA is in the input but is in fact a DFA; this would be DLOG-complete.)

And counting accepting paths on one particular input: if the NFA is part of the input, it is #L-complete, if the NFA is fixed, this is computable in #NC^1 and hence in deeterminstic logspace.

August 29, 2009 12:06 pm

Thanks for the post(s). I have known the result for a long time, and cannot remember how first heard it. So thanks for the comments, again.

5. August 29, 2009 11:51 am

mistyped URL

6. August 29, 2009 12:53 pm

About 10 years ago, I found a false proof that P does not equal NP, and it took me a few days to find my bug (I was pretty excited for a while!). Even though I had already found my bug, I showed the false proof, just for fun, to various famous members of our theory community, to see if they could spot the bug (I did tell them that there existed a bug, and that their challenge was to find it). Only two of them were able to find the bug, and they both found it pretty quickly – Larry Stockmeyer and Moshe Vardi. Amusingly enough, the bug was, of all things, a misuse of Fagin’s Theorem! Maybe the other people I showed the proof to just trusted that I surely wouldn’t misuse my own theorem.

7. September 17, 2009 4:58 am

hello,

thanks for the great quality of your website, each time i come here, i’m amazed.

I would like to suggest you to discover the real black hattitude.
you’ll find a lot of tricks related to the black hattitude,

You can buy some black hattitude, rent black hattitude, steal black hattitude, or find
the ultimate black hattitude on our sites ofblack hattitude.

regards,

Mike Litoris

black hattitude

you’ll find here also some good black hattitude