Circuit Evaluation over Monoids (CEM)

Input

A finite monoid $(M, \oplus, 1)$ containing a nonsolvable group; an encoding $\overline{\alpha}$ of a circuit $\alpha$, whose gates are of type $\oplus$, inputs $x_1, \ldots, x_n \in M$, and designated output $y$.

Problem

Does $\alpha$ evaluate to $y$ on input $x_1, \ldots, x_n$?

Definitions

See CVP. Set $M$ is finite, $\oplus$ is an associative binary operation on the elements of $M$, and $1$ acts as an identity element.

Status

$\P$-complete (Beaudry, McKenzie, and Péladeau [1]).

Remarks

The reduction to show hardness is from CVP. If $M$ is solvable the same problem is in $\mathsf{DET}$, the class of problems $\NC^1$ Turing reducible to computing integer determinants.