The circuit value problem (or circuit evaluation problem) is the computational problem of computing the output of a given Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inpu ...
on a given input.
The problem is complete for P under uniform AC reductions. Note that, in terms of time complexity
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
, it can be solved in linear time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
simply by a topological sort.
The Boolean formula value problem (or Boolean formula evaluation problem) is the special case of the problem when the circuit is a tree. The Boolean formula value problem is complete for NC.Author's draft
The problem is closely related to the
Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisf ...
which is complete for NP and its complement, the propositional tautology problem, which is complete for co-NP
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and o ...
.
See also
* Circuit satisfiability *Switching lemma In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. It was first introduced by Johan Håstad to prove that AC0, AC0 Boolean circuits of depth ''k'' requ ...
References
* Polynomial-time problems Computational problems Theoretical computer science {{compu-prog-stub