|
Un '''circuito Booleanobooleano''' è un modello matematico di [[computazione]] usato nello studio della [[teoria della complessità computazionale]]. Questi circuiti sono principalmente oggetto di studi nella [[complessità dei circuiti]] e sono dei tipi speciali di [[circuiti]]; un [[linguaggio formale (matematica)|linguaggio formale]] può essere deciso da una famiglia di circuiti Booleanibooleani, un circuito per ogni possibile lunghezza di input. In aggiunta, essi sono usati come modello formale per [[logica combinatoria]] in [[elettronica digitale]].
I circuiti Booleanibooleani 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 [[Funzionefunzione booleana|funzione Booleana]] che prende ''k'' bit di input e invia in output un singolo bit.
==Definizione formale==
Nel dare una definizione formale di circuiti Booleanibooleani, [[Heribert Vollmer|Vollmer]] comincia definendo un insieme base di funzioni Booleanebooleane ''B'', corrispondenti alle porte accettabili nel modello del circuito. Un circuito Booleanobooleano su una base ''B'', con ''n'' input e ''m'' output, è definita come un [[grafo aciclico diretto]] finito. Ogni vertice corrisponde o ad una funzione base o ad un input, e c'è un set di esattamente ''m'' nodi che sono etichettati come output.<ref>Vollmer 1999, p. 8.</ref> Gli archi devono anche essere in qualche modo ordinati, per distinguere tra differenti argomenti per la stessa funzione Booleanabooleana.<ref>Vollmer 1999, p. 9.</ref>
== Complessità computazionale ==
=== Valutazione di un circuito ===
Il problema ''CIRCUIT-EVAL'' prende come input la descrizione di un circuito Booleanobooleano e un'assegnazione di valore di verità alle variabili del circuito, e accetta il test solo se il circuito restituisce vero. ''CIRCUIT-EVAL'' è [[P-completo]].<ref>Arora & Barak 2009, p. 119.</ref>
=== Misure di complessità ===
{{vedi anche|Complessità dei circuiti}}
Varie importanti [[Misura di complessità|misure di complessità]] possono essere definite sui circuiti Booleanibooleani, comprese la profondità del circuito, la dimensione del circuito e il numero di alternanze tra porte AND e porte OR. Per esempio, la complessità di dimensione di un circuito Booleanobooleano è il numero selle porte.
== Classi di complessità ==
{{Torna a|Complessità dei circuiti#Classi di complessità{{!}}Classi di complessità dei circuiti}}
Varie importanti classi di complessità sono definite in termini di circuiti Booleanibooleani, compreso [[NC (complessità)|NC]]. NC è definito come l'insieme delle [[Funzione booleana|funzioni Booleanebooleane]] che possono essere decise da circuiti Booleanibooleani 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.
== Note ==
| 