I circuiti Booleani sono definiti in termini di [[porte logiche|porte]] che essi contengono. Ad esempio, un circuito potrebbe contenere porte AND e OR [[funzioni binarie|binarie]] e porte NOT [[unarie]], o essere interamente descritti da [[porte NAND]] binarie. Ogni porta corrisponde a qualche [[funzione Booleana]] che prende ''k'' bits di input e invia in output un singolo bit.
Diverse importanti misure di complessità possono essere definite su circuiti Booleani, incluso profondità di circuito, dimensione di circuito o numero di alternanze. In una famiglia di circuiti, consideriamo la complessità (misurata in dimensione del circuito), per esempio, come la funzione di n che da la dimensione del circuito che decide l'input di lunghezza n.
Diverse importanti classi di complessità sono definite in termini di circuiti Booleani, incluso [[NC (complessità)|NC]]. NC è definita essere il set di [[funzioni Booleane]] che possono essere decise da circuiti Booleani uniformi di dimensione polinomiale e profondità polilogaritmica. Qui, la parola ''uniforme'' significa che deve esserci qualche condizione sulla famiglia di circuiti di modo che una descrizione di un circuito può essere fatta dal suo indice, n.
