Stockmeyer’s Approximate Counting Method
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 ”
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.
Suppose that is a circuit with inputs of size polynomial in . Then, a natural question is: How many satisfy ? 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 so that ? Let .
A key observation is that there is an amplifier lurking here: if we can in general determine to within a factor of in polynomial time, then we can determine it to within factor for any constant also in polynomial time. This can be proved by a simple amplification argument. The idea is this: create a new circuit where and are disjoint inputs.
Then, has inputs that it accepts. If you know to a factor of , then you know to a factor of . An -fold version of this will yield a approximation of
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 to within a factor of . Larry proves,
Theorem: There is a random algorithm that determines to within a factor of 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 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 be the circuit and let be the set of inputs so that . Suppose that our goal is really modest: we want to know if is really large, or really small. Take a random hash function where is much smaller than . Then, check to see if there are two distinct and so that they form a “collision”,
and both are in . If is small then, it is likely that (1) will have no solutions, but if 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 and such that and both are in ”?
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 is a -state deterministic finite state automaton. Then, the number of length inputs that are accepted by can be computed exactly in polynomial time in and .
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 be a new automata that simulates on all inputs of length , and has the property that the state diagram is acyclic. Essentially, replaces each state of by the state where . For example, if was a transition on input , then
is a transition for input for all . We have simply unrolled the automaton to avoid any loops: this cannot be done in general, but is fine if we are only concerned with inputs of a fixed length .
The algorithm then inductively labels each state with the number of length- inputs that reach this state. To label a state , we take each state with arcs to , and add the number of times the number of arcs from to . The number of accepting computations of length is then the sum of the numbers for with an accepting state of the original .
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.