This research investigates complexity theory from the point of view of boolean circuits with an emphasis on the area of lower bounds. Boolean circuits are natural models of parallel computation. The depth of circuits corresponds to parallel time while the size of circuits corresponds to the number of processors. Viewed from complexity theory, the size of boolean circuits corresponds to time in Turing machines. Thus questions such as P=NP? or NC=P? will be solved, perhaps, only after a better understanding of how to prove lower bounds to the complexity of boolean functions is obtained. This is the main objective of this project.
