Monotone Circuit Value Problem (MCVP)

Input

An encoding $\overline{\alpha}$ of a Boolean circuit $\alpha$, inputs $x_1, \ldots, x_n$ and designated output $y$, with the additional assumption that $\alpha$ is monotone. That is, it is constructed solely of INPUT, AND and OR 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 [3, Theorem 6.2.2], Goldschlager [1]).

Remarks

The reduction to show hardness is from CVP or GMSP. It remains complete when the fan-in and fan-out is 2, which is often implied in several reductions, while the more technically correct term would be M2CVP. Vitter and Simmons give a $\sqrt{n}$ time parallel algorithm for the non-sparse version of the problem [2].