View article

An algebra A is finitely presented if there is a finite set G of generator symbols, a finite set O of operator symbols, and a finite set Γ of defining relations xΞy where x and y are well-formed terms over G and O, such that A is isomorphic to the free algebra on G and O modulo the congruence induced by Γ.

The uniform word problem, the finiteness problem, the triviality problem (whether A is the one element algebra), and the subalgebra membership problem (whether a given element of A is contained in a finitely generated subalgebra of A) for finitely presented algebras are shown to be ≤^m_log-complete for P. The schema satisfiability problem and schema validity problem are shown to be ≤^m_log-complete for NP and co-NP, respectively. Finally, the problem of isomorphism of finitely presented algebras is shown to be polynomial time many-one equivalent to the problem of graph isomorphism.