Finitely Generated Subalgebra (FGS)
Category: Algebra
Input
A finitely presented algebra $A = (M, \mathcal{A}, \Gamma)$ and terms $x_1, \ldots, x_n, y$. Let $[x] = \{y \in \tau \mid x \equiv y\}$.
Problem
Is $[y]$ contained in the subalgebra generated by $[x_1], \ldots, [x_n]$?
Definitions
See UWPFPA.
Status
$\P$-complete (Kozen [1]).
Remarks
A polynomial time algorithm for the problem is given in [1]. The reduction to show hardness is from GEN.