Circuito booleano: differenze tra le versioni

Versione delle 17:52, 23 apr 2018

Versione attuale delle 12:17, 8 feb 2024

(2 versioni intermedie di 2 utenti non mostrate)

Riga 1:

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 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 [[funzione booleana]] che prende ''k'' bit di input e invia in output un singolo bit.

Riga 8:

== Complessità computazionale ==

=== 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>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 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 selledelle porte.

== Classi di complessità ==

Riga 22:

== Bibliografia ==

* {{cita libro | cognome = Vollmer | nome = Heribert | titolo = Introduction to Circuit Complexity | url = https://archive.org/details/introductiontoci0000voll | anno = 1999 | editore = Springer | città = Berlino | isbn = 3-540-64310-9}}

* {{cita libro | cognome1 = Arora | nome1 = Sanjeev | cognome2 = Barak | nome2 = Boaz | titolo = Computational Complexity: A Modern Approach | anno = 2009 | editore = Cambridge University Press | città = New York | isbn = 0-521-42426-7}}