Topologically Ordered Circuit Value Problem (TopCVP)

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 the vertices in the circuit are numbered and listed in topological order.

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 [1, Theorem 6.2.1]).

Remarks

The reduction to show hardness is from GMSP. Most circuit value reductions preserve topological ordering, so the restrictions of most variants of the Circuit Value Problem to topologically ordered instances remain $\P$-complete.