Circuito booleano

Da Wikipedia, l'enciclopedia libera.

Un circuito booleano è 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 può essere deciso da una famiglia di circuiti booleani, un circuito per ogni possibile lunghezza di input. In aggiunta, essi sono usati come modello formale per logica combinatoria in elettronica digitale.

I circuiti booleani sono definiti in termini di porte che essi contengono. Ad esempio, un circuito potrebbe contenere porte AND e OR binarie e porte NOT unarie, o essere interamente descritti da porte NAND binarie. Ogni porta corrisponde a qualche funzione booleana che prende k bit di input e invia in output un singolo bit.

Definizione formale[modifica | modifica wikitesto]

Nel dare una definizione formale di circuiti booleani, Vollmer comincia definendo un insieme 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.[1] Gli archi devono anche essere in qualche modo ordinati, per distinguere tra differenti argomenti per la stessa funzione booleana.[2]

Complessità computazionale[modifica | modifica wikitesto]

Valutazione di un circuito[modifica | modifica wikitesto]

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.[3]

Misure di complessità[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Complessità dei circuiti.

Varie importanti 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à[modifica | modifica wikitesto]

Varie importanti classi di complessità sono definite in termini di circuiti booleani, compreso NC. NC è definito come l'insieme delle 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.

Note[modifica | modifica wikitesto]

  1. ^ Vollmer 1999, p. 8.
  2. ^ Vollmer 1999, p. 9.
  3. ^ Arora & Barak 2009, p. 119.

Bibliografia[modifica | modifica wikitesto]

  • Heribert Vollmer, Introduction to Circuit Complexity, Berlino, Springer, 1999, ISBN 3-540-64310-9.
  • Sanjeev Arora e Boaz Barak, Computational Complexity: A Modern Approach, New York, Cambridge University Press, 2009, ISBN 0521424267.

Voci correlate[modifica | modifica wikitesto]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica