Circuito booleano: differenze tra le versioni

Versione delle 17:26, 1 ott 2012

Versione delle 17:27, 1 ott 2012

Riga 6:

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.

==Definizione formale==

Nel dare una definizione formale di circuiti Booleani, [[Heribert Vollmer|Vollmer]] comincia definendo un set base di funzioni Booleane ''B'', corrispondenti alle porte accettabili nel modello del circuito. Un circuito Booleano 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 Booleana.<ref>Vollmer 1999, p. 9.</ref>

== Valutazione di un circuito ==

Il problema ''CIRCUIT-EVAL'' prende come input la descrizione di un circuito Booleano 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>S. Arora, B. Barak, ''Computational complexity, a modern approach'', page 119</ref>

== Note ==