Circuito booleano: differenze tra le versioni

Versione delle 16:30, 13 gen 2024

Versione attuale delle 12:17, 8 feb 2024

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