NAND Circuit Value Problem (NANDCVP)

Input

An encoding $\overline{\alpha}$ of a Boolean circuit $\alpha$, inputs $x_1, \ldots, x_n$ and an output gate $y$. Circuit $\alpha$ is constructed only of NAND gates and is restricted to have fanout two for inputs and NAND gates.

Problem

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

Definitions

See CVP.

Status

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

Remarks

The reduction to show hardness is from AM2CVP. Any complete basis of gates suffices, by the obvious simulation of NAND gates in the other basis. For example, NOR gates form a complete basis. NORCVP is defined analogously to NANDCVP. See Post for a characterization of complete bases [1]. See the remarks for CVP for other bases, not necessarily complete, for which the associated CVP is still complete.