Problema de valor del circuito

El problema del valor del circuito (o problema de evaluación del circuito) es el problema computacional de calcular la salida de un circuito booleano dado a partir de una entrada dada.

El problema está completo para P bajo reducciones uniformes AC ^0. Nótese que, en términos de complejidad temporal , se puede resolver en tiempo lineal simplemente mediante una ordenación topológica .

El problema del valor de la fórmula booleana (o problema de evaluación de la fórmula booleana) es el caso especial del problema cuando el circuito es un árbol. El problema del valor de la fórmula booleana es completo para NC ¹ con respecto a las reducciones AC ^{0. [ 1 ]}

El problema está estrechamente relacionado con el problema de satisfacibilidad booleana, que es completo para NP , y su complemento, el problema de tautología proposicional , que es completo para co-NP .

• Satisfacibilidad del circuito
• Lema de conmutación

• Richard E. Ladner (enero de 1975). "El problema del valor del circuito es logaritmo completo en espacio para P". ACM SIGACT News . 7 (101): 18– 20. doi : 10.1145/990518.990519 .