Given a finite acyclic Boolean circuit and its input assignment, determine the output bit. Topological gate evaluation places the problem in P; it is a standard P-complete problem under logspace many-one reductions. Boolean circuit evaluation is different from Circuit satisfiability problem, which asks whether some assignment succeeds.
The circuit value problem restricted to AND and NOT gates remains P-complete. Replace each OR by , using a constant-size gadget. Gate indices and gadget positions can be emitted in logarithmic space, and assignments are preserved. Constants, when needed, can be represented by fixed-valued input nodes.
Articles by others on the same topic
The Circuit Value Problem (CVP) is a decision problem in computer science, particularly in the fields of complexity theory and cryptography. In general terms, the problem can be described as follows: Given a Boolean circuit (a network of logical gates) and a specific input assignment, the goal is to determine the output of the circuit for that input.