Generability (GEN)

Input

A finite set $W$, a binary operation $\bullet$ on $W$ (presented as a table), a subset $V \subseteq W$, and $w \in W$.

Problem

Is $w$ contained in the smallest subset of $W$ that contains $V$ and is closed under the operation $\bullet$?

Status

$\P$-complete under $\NC^1$ reductions (Jones and Laaser [1], Barrington and McKenzie [2]).

Remarks

The reduction to show hardness is from UNIT or CVP. The problem remains $\P$-complete if $V$ is a singleton set and $\bullet$ is commutative (Barrington and McKenzie [2], [1]). If $\bullet$ is associative, GEN is complete for $\mathsf{NLOG}$. The problem remains in $\P$ even with more than one operation.

The complexities of several other versions of GEN are addressed in [2]. Under the appropriate definitions, it is known that approximating this problem is also $\P$-complete (Serna and Spirakis [3]). Simons developed an $O(n)$ time parallel algorithm for the problem in 1987, where $n = |W|$ [5].