Approximate Counting

This week I have been at the IPAM workshop on expander graphs, scheduled so that we could spend Valentine’s day attending lectures, thus symbolically demonstrating our love for math.

My talk was on the problem of checking whether a given hypergraph is an expander, focusing on the expansion property that is known as “quasirandomness.”

Because of the workshop, my Complexity class took a one-week break.

Last week, we talked about one of my favorite “elementary” results in complexity theory: approximate counting with an NP oracle.

Suppose that someone comes up with a polynomial time algorithm for SAT and proves that P=NP; then we know that a number of awesome consequences would follow (and some frightening ones, such as the impossibility of cryptography). We would still, however, not be able to solve combinatorial counting problems such as: given a graph, how many proper 3-colorings does it have, if any?

If the number of colorings is k, we can compute it in time polynomial in k, because the question “is the number of colorings at least t?” can be reduced to a SAT instance of size polynomial in t and in the size of the graph. We might, however, be given a graph with n vertices and a number of 3-colorings in the ballpark of 2^n. Then, even the awesome power of a polynomial time algorithm for SAT does not seem to help. Indeed it follows from Toda’s Theorem that, if one could solve the 3-coloring counting problem efficiently using a SAT oracle, then the polynomial hierarchy would collapse. (If the previous sentence did not make sense to you, let’s just say that there is good evidence that there is no algorithm that solves the 3-coloring counting problem efficiently by “just relying” on an efficient algorithm for SAT.)

Interestingly enough, however, we can approximately count solutions to any NP problem in probabilistic polynomial time, given an oracle for SAT. The idea is cleverly simple. Continue reading