Synchronous Alternating Monotone Fanout 2 CVP (SAM2CVP)

Input

An encoding $\overline{\alpha}$ of a Boolean circuit $\alpha$, inputs $x_1, \ldots, x_n$ and designated output $y$. In addition to the restrictions of AM2CVP, this version requires the circuit to be synchronous.

Problem

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

Definitions

See CVP. A circuit is synchronous if each level in the circuit can receive its inputs only from gates on the preceding level.

Status

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

Remarks

The reduction to show hardness is from AM2CVP.