Circuit Value Problem (CVP)

Input

An encoding $\overline{\alpha}$ of a Boolean circuit $\alpha$, inputs $x_1, \ldots, x_n$ and designated output $y$.

Problem

Is output $y$ of $\alpha$ true on inputs $x_1, \ldots, x_n$?

Definitions

A Boolean circuit $\alpha$ is a labeled directed acyclic graph. Each vertex (gate) is labeled INPUT, AND, OR, or NOT, and computes its corresponding function over its $n$ inputs, whose values are given as $x_1, \ldots, x_n \in \{0,1\}$. An encoding $\overline{\alpha}$ of $\alpha$ is a string from $\{0,1\}^\ast$ where the vertices of $\alpha$ are listed with their types and connections, not necessarily in topological order.

Status

$\P$-complete under $\NC^1$ reductions (Greenlaw, Hoover and Ruzzo [3, Theorem 4.2.2], Ladner [1]).

Remarks

The CVP is the most fundamental $\P$-complete problem, in fact, it’s one of the few where $\P$-completeness is proved directly (from GMSP) instead of through reductions from other $\P$-complete problems.

For the two input basis of Boolean functions, it is known that CVP is $\P$-complete except when the basis consists solely of or, consists solely of and, or consists of any or all of the following: XOR, EQUIVALENCE, and NOT (Goldschlager and Parberry [2]).