Circuito booleano: differenze tra le versioni

Versione delle 12:54, 24 apr 2013

Versione delle 01:11, 18 mar 2014

Riga 10:

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>

== ValutazioneComplessità di un circuitocomputazionale ==

=== 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>

=== Misure di complessità ===

{{vedi anche|Complessità dei circuiti}}

Varie importanti [[Misura di complessità|misure di complessità]] possono essere definite sui circuiti Booleani, 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 Booleano è il numero selle porte.

== Classi di complessità ==

{{main|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 dedise 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 tale che la descrizione di un circuito possa essere computata soltanto dal numero degli input al circuito.

== Note ==