Decidability of classes of algebraic systems in polynomial time
Mikhail Igorevich Anokhin · Sbornik Mathematics · 2002
For some classes of algebraic systems several kinds of polynomial-time decidability are considered, which use an oracle performing signature operations and computing predicates. Relationships between various kinds of decidability are studied. Several results on decidability and undecidability in polynomial time are proved for some finitely based varieties of universal algebras.