Alternating Monotone Fanin 2, Fanout 2 CVP (AM2CVP)

Input

An encoding $\overline{\alpha}$ of a Boolean circuit $\alpha$, inputs $x_1, \ldots, x_n$ and designated output $y$. On any path from an input to an output the gates are required to alternate between OR and AND gates. Inputs are required to be connected only to OR gates, and outputs must come directly from OR gates. The circuit is restricted to have fanout exactly two for inputs and internal gates, and to have a distinguished OR gate as output.

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.3]).

Remarks

The reduction to show hardness is from MCVP. Goldschlager, Shaw, and Staples gave a $\P$-completeness proof for Monotone, Fanout 2 CVP [1].