Circuit Computations
Circuit computations will now be considered.
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.
