Stockmeyer’s Approximate Counting Method

August 27, 2009

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.

Stockmeyer’s Approximate Counting Method

Stockmeyer’s Approximate Counting Method

Like this:

Recommend

请问怎么用eth在dapp里购买东西呢？weth是怎么转换eth的？ | 登链社区 | 技术问答

董车日报｜Model 3/Y 全系售价提高 1000 美元 / 理想 NOA 辅助驾驶测试图曝光 / 首个...

What’s New in Submitting Your SAP Innovation Awards 2022 Entry

苹果正在给 iPhone 测试一个救命功能，或许明年就能用上

福建省评选首批乡村振兴直播产业基地建设扶持项目

爱奇艺用Grass Valley 4K转播车带动生产

MySQL -- Online DDL

《天书奇谭4K纪念版》成都首映主创含泪分享影迷感叹“爷青回”！

【快讯】广东IPTV平台4K内容量已超1万小时，8K专区即将上线

一个低学历程序员开发逆袭大厂的心路历程，看完真心给跪了

About Joyk