6 - Boolean circuits

Summary

One might imagine that P ≠ NP, but SAT is tractable in the following sense: for every ℓ there is a very short program that runs in time ℓ² and correctly treats all instances of size ℓ.

– Karp and Lipton, 1982

This chapter investigates a model of computation called the Boolean circuit, which is a generalization of Boolean formulas and a simplified model of the silicon chips used to make modern computers. It is a natural model for nonuniform computation, which crops up often in complexity theory (e.g., see Chapters 19 and 20). In contrast to the standard (or uniform) TM model where the same TM is used on all the infinitely many input sizes, a nonuniform model allows a different algorithm to be used for each input size. Thus Karp and Lipton's quote above refers to the possibility that there could be a small and efficient silicon chip that is tailor-made to solve every 3SAT problem on say, 100,000 variables. The existence of such chips is not ruled out even if P ≠ NP. As the reader might now have guessed, in this chapter we give evidence that such efficient chip solvers for 3SAT are unlikely to exist, at least as the number of variables in the 3CNF formula starts to get large.