Circuit booleà
En teoria de la complexitat, un circuit booleà és un model matemàtic d'un circuit digital. Un llenguatge formal pot ser resolt per una família de circuits booleans, un circuit per cada possible longitud d'entrada. Els circuits booleans també s'usen com a model formal pels circuits combinacionals en electrònica digital.
Un circuit booleà es descriu per les portes lògiques que conté. Per exemple, un circuit pot estar format per portes binàries AND i OR i portes unàries NOT, o estar completament format per portes binàries NAND. Cada porta es correspon a un funció booleana que té un cert nombres de bits d'entrada i treu un sol bit.
Els circuits booleans proporcionen un model per molts components digitals usats en enginyeria informàtica, incloent multiplexors, sumadors i unitats aritmeticològica.
Definició formal modifica
Primer es pot definir un conjunt bàsic B de funcions booleanes, que es corresponen a les ports permeses en el model del circuit. Un circuit booleà sobre la base B, amb n entrades i m sortides es defineix com un graf dirigit acíclic. Cada vèrtex es correspon a una funció bàsica o una entrada, i hi ha un conjunt de m nodes etiquetats com a sortides. Les arestes han de tenir també alguna ordenació, per poder distingir entre diferents arguments per la mateixa funció booleana.[1]
Com a cas particular, una fórmula proposicional o expressió booleana és un circuit booleà amb una sola sortida on cada altre node té un fan-out d'1. Per tant, un circuit booleà es pot veure com una generalització que permet compatir subfórmules i múltiples sortides.
Un conjunt bàsic molt habitual és el conjunt {AND, OR i NOT}, amb el qual es pot construir qualsevol funció booleana.
Complexitat computacional modifica
Avaluació d'un circuit modifica
El problema d'avaluació d'un circuit, el problema d'avaluar el resultat d'un circuit booleà segons una entrada donada, és un problema P-complet. Per tant, aquest problema es considera inherentment seqüencial en el sentit que no hi ha un algorisme paral·lel prou eficient que el pugui resoldre.
Mesures de complexitat modifica
Es defineixen diferents mesures de complexitat sobre els circuits booleans, incloent la profunditat del circuit, la mida del circuit, i el nombre d'alternacions entre portes AND i OR.
Classes de complexitat modifica
Força classes de complexitat es defineixen utilitzant circuits booleans, com per exemple la classe NC. Aquesta classe es defineix com el conjunt de funcions booleanes que es poden decidir per un circuit booleà uniforme de mida polinòmica i profunditat polilogarítmica. Per uniforme s'entén de que hi ha certes condicions a la família de circuits de manera que una descripció del circuit es pot computar a partir del nombre d'entrades del circuit.
Vegeu també modifica
Referències modifica
- ↑ 1964-, Vollmer, Heribert,. Introduction to circuit complexity : a uniform approach. Berlín: Springer, 1999. ISBN 3540643109.