Complexity of finitely presented algebras

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 &Ggr; of defining relations x&Xgr;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 &Ggr;. 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 ≤mlog-complete for P. The schema satisfiability problem and schema validity problem are shown to be ≤mlog-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.