Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Circuit value problem

Computational problem

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated June 19, 2025
Image credit is listed at the end of this article.

The circuit value problem (or circuit evaluation problem) is the computational problem of computing the output of a given Boolean circuit on a given input.

The problem is complete for P under uniform AC0 reductions. Note that, in terms of time complexity, it can be solved in linear time 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 NC1 with respect to AC0 reductions.

The problem is closely related to the Boolean satisfiability problem which is complete for NP and its complement, the propositional tautology problem, which is complete for co-NP.

Watch videos about Circuit value problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Circuit value problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Circuit satisfiability problem

In theoretical computer science, the circuit satisfiability problem is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true. In other words, it asks whether the inputs to a given Boolean circuit can be consistently set to 1 or 0 such that the circuit outputs 1.

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 Boolean circuits of depth k require size exp ⁡ ) ) {\displaystyle \exp(\Omega (n^{1/(k-1)}))} to compute the parity function on n {\displaystyle n} bits.