Circuito booleano: differenze tra le versioni

Versione delle 01:24, 18 mar 2014

Versione delle 01:25, 18 mar 2014

Riga 12:

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