Finitely Presented Algebras Triviality (FPAT)
Category: Algebra
Input
A finitely presented algebra $A = (M, \mathcal{A}, \Gamma)$.
Problem
Is $A$ trivial?
Definitions
See UWPFPA. An algebra $A$ is trivial if it contains only one element.
Status
$\P$-complete (Kozen [1]).
Remarks
A polynomial time algorithm for the problem is given in [1]. The reduction to show hardness is from MCVP.