Planar Circuit Value Problem (PCVP)

Input

An encoding $\overline{\alpha}$ of a planar Boolean circuit $\alpha$, inputs $x_1, \ldots, x_n$ and designated output $y$.

Problem

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

Definitions

See CVP. A planar circuit is one whose graph can be drawn in the plane with no edges crossing.

Status

$\P$-complete under $\NC^1$ reductions (Goldschlager [1]).

Remarks

The reduction to show hardness is from CVP and it’s done via a planar cross-over circuit using planar XOR circuits. Monotone planar cross-over circuits do not exist, and in fact the monotone version of PCVP is in $\mathsf{LOGCFL} \subseteq \NC^2$ when all inputs appear on one face of the planar embedding (Dymond and Cook [2][3], Goldschlager [4], Mayr [5]). The more general problem where inputs may appear anywhere is also in $\NC$ (Delcher and Kosaraju [6], Kosaraju [7]). A complete characterization of all bases from which it is possible to construct planar cross-over circuits is given in McColl [8].