In this lecture we prove the Karp-Lipton theorem that if all NP problems have polynomial size circuits then the polynomial hierarchy collapses. A nice application is a theorem of Kannan, showing that, for every , there are languages in requiring circuits of size . The next result we wish to prove is that all approximate combinatorial counting problem can be solved within the polynomial hierarchy. Before introducing counting problems and the hashing techniques that will yield this result, we prove the Valiant-Vazirani theorem that solving SAT on instances with exactly one satisfying assignment is as hard as solving SAT in general.
In this lecture we introduce the computational model of boolean circuits and prove that polynomial size circuits can simulate all polynomial time computations. We also begin to talk about randomized algorithms.
Suppose that is an arbitrary boolean function, and that we want to construct (or rather, show the existence of) a circuit of size that approximates as well as possible. How well can we hope to do?
Certainly, we can get a -size circuit that computes on of the inputs, by either choosing the circuit that always outputs 0 or the circuit that always outputs 1.
Also (ignoring factors), we can construct a circuit that has hardwired the values of at places, and then outputs always zero or always one (whichever is better) on the remaining inputs. This circuit will work on a
fraction of inputs, and this seems like the best we can hope for.
We may then try to prove the optimality of the above construction by considering a random function , using the Chernoff bound to show that, for a fixed circuit of size , and have agreement less than except with probability less than , and then taking a union bound over the roughly circuits of size . (It’s actually , but we said we would ignore .) Unfortunately, this calculation only leads us to a proof that, in general, we cannot hope to compute a random function on more than a
fraction of inputs using a circuit of size . This is a disappointment because we were hoping to prove that (1) was tight.
If we think about it, however, we see that the bound in (2) is actually typically achievable for a random function: partition the possible inputs into blocks, each of size . (Based, for example, on the value of the first bits.) Now, the value of in each block are just a sequence of random bits, so, with constant probability, there is either an excess of ones or an excess of zeroes. For each block, hard-wire into the circuit the majority value of among elements of the block. Clearly we are getting an fraction of inputs correct, and our circuit has size .
What about general functions? Is it possible to do better than (1) for every function?