Circuit Complexity
Boolean circuits certainly resemble the kinds of circuits, now used to build computers, more closely than Turing machines — making it reasonable to consider how things change if these are used to define the underlying model of computation.
To begin, Boolean circuits will be introduced, and their use to represent Boolean functions will be considered. These will be used to define a Circuit Value Problem whose language of Yes-instances is P-complete.
A single Boolean circuit must have a fixed number of inputs. However, circuit families can be used to compute Boolean functions with arbitrarily many inputs as well. By introducing simple encoding schemes, these can be used to represent algorithms to decide membership in languages (over arbitrary alphabets) — and they form another model for computation that is significantly different from a Turing machine. Complexity classes based on computations with circuit families will be introduced, and relationships between these and complexity classes that we already know about will be explored.
Lecture #21: Introduction to Boolean Circuits
Why This is Included
As noted above, Boolean circuits resemble the kinds of circuits, now used to build computers, more closely than Turing machines — making it reasonable to consider how things change if these are used as the underlying model of computation. It is necessary to define these reasonably precisely in order to do this — and this is the goal for the material at the beginning of this lecture.
It happens that a “P-complete” problem (and language of Yes-instances) emerges as soon as this material has been introduced. Knowing about this language will be helpful when investigating the structure of the complexity class P (and identifying the “hardest” languages in this class).
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #22: Circuit Families and Their Properties
Why This is Included
While Boolean circuits are, in some ways, more similar to computer hardware than Turing machines — and this is a reason for studying them — two issues must be addressed if they are to be considered as devices that might decide languages, as Turing machines can:- They accept Boolean inputs, while Turing machines accept strings of symbols over arbitrary alphabets, instead.
- A Boolean circuit accepts a fixed number of inputs, while Turing machines can process input strings of arbitrary length.
These issues are considered in order to obtain a circuit-based model of computation, including circuit families, which can decide languages like Turing machines can.
Results from the previous lecture would suggest that circuit families with polynomial size should be considered as we try to identify a (circuit-based) complexity class to be compared with P. By doing so a new complexity class, “P/Poly”, is defined.
If a “uniformity condition” is also imposed (so that only a restricted set of circuit families are allowed) then it turns out that an alternative characterization of the complexity class “P”, involving circuit families, can be established. However, P is a proper subset of P/Poly — and this new complexity class may be of interest because of the possibility that it includes languages (and associated problems) that are outside the complexity class P while still being — in some useful sense — “efficiently computable”.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #23: More about Circuit Complexity
Why This is Included
Questions that were considered, when circuit complexity was investigated, included the following:
-
Which Boolean functions have circuit families of a given size? By how much does increasing size bounds expand the set of Boolean circuits with circuit families?
-
Do “intractable” problems — including problems whose languages of Yes-instances are NP-complete, or even complete for EXPTIME, have polynomial-size circuit families? What else could be concluded if they did?
This lecture presents some (reasonably early) results concerning these questions, in order to give a somewhat more complete representation of what is known about circuit complexity.
