Circuito booleano: differenze tra le versioni

Versione delle 01:28, 18 mar 2014

Versione delle 01:33, 18 mar 2014

Riga 19:

== Classi di complessità ==

{{mainTorna a|Complessità dei circuiti#Classi di complessità{{!}}Classi di complessità dei circuiti}}

Varie importanti classi di complessità sono definite in termini di circuiti Booleani, compreso [[NC (complessità)|NC]]. NC è definito come l'insieme delle [[Funzione booleana|funzioni Booleane]] che possono essere decise da circuiti Booleani uniformi di dimensione polinomiale e profondità polilogaritmica. Qui, la parola ''uniforme'' significa che ci deve essere una qualche condizione sulla famiglia di circuiti in modo che la descrizione di un circuito possa essere computata soltanto dal numero degli input al circuito.