Circuit complexity is a branch of computational complexity theory that studies the size and depth of Boolean circuits used to compute Boolean functions. It is used to separate complexity classes, such as P and NP, and define classes such as AC0, AC, TC0, NC1, NC, and P/poly. Lower bounds on the size of Boolean circuits are used to prove these separations.
Carnegie Mellon University
Spring 2023
This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.
No concepts data
+ 29 more concepts