Computational complexity of some problems involving congruences on algebras

DOI10.1016/S0304-3975(01)00009-3zbMath0988.68082WikidataQ60143374 ScholiaQ60143374MaRDI QIDQ5958321

Giora Slutzki, Clifford Bergman

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Subalgebras, congruence relations (08A30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Automorphisms and endomorphisms of algebraic structures (08A35)

Related Items (1)

The computational complexity of deciding whether a finite algebra generates a minimal variety

Cites Work

• Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
• Symmetric space-bounded computation
• Space-bounded reducibility among combinatorial problems
• Complete problems for deterministic polynomial time
• On full embeddings of categories of algebras
• Relationships between nondeterministic and deterministic tape complexities
• Languages that Capture Complexity Classes
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computational complexity of some problems involving congruences on algebras