Complexity of some problems in universal algebra. Extended abstract

DOI10.1007/3-540-49116-3_15MaRDI QIDQ4251048zbMATH OpenFDO

Authors Clifford Bergman, Giora Slutzki

Publication date 29 November 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-49116-3_15

zbMATH Keywords

2-variable algebrasclones of term operationscomputational complexityfinite algebraic structures of finite similarity typeidentitiesquasi-identitiesunary algebras

Mathematics Subject Classification ID

Word problems (aspects of algebraic structures) (08A50) Unary algebras (08A60) Finitary algebras (08A62) Quasivarieties (08C15) Analysis of algorithms and problem complexity (68Q25)

Review text

The paper studies the computational complexity of some basic problems involving finite algebraic structures of finite similarity type. The main results: 1) Given two finite algebras, the problem whether they satisfy the same identities is in 2-EXPTIME; whether they satisfy the same quasi-identities is NP-complete; whether they have the same clones of term operations is EXPTIME-complete. 2) The same problems for unary algebras are respectively PSPACE, NP, and PSPACE-complete, and for 2-variable algebras the complexities are L, L, and NL. Some open questions regarding the exact complexities of some of these results are posed. For the entire collection see [Zbl 0909.00052].

Recommendations

• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• scientific article; zbMATH DE number 3872682
• Computers and universal algebra: Some directions

Cited in

(22)

• Computing congruences efficiently
• Testing for a semilattice term
• Computers and universal algebra: Some directions
• The complexity of homomorphism factorization
• Complexity of the universal theory of modal algebras
• Complexity of the normalization of algebras
• Computational complexity of various Mal'cev conditions
• The complexity of problems connected with two-element algebras
• Unifiability and admissibility in finite algebras
• scientific article; zbMATH DE number 3867395 (Why is no real title available?)
• scientific article; zbMATH DE number 3872682 (Why is no real title available?)
• scientific article; zbMATH DE number 4154512 (Why is no real title available?)
• On Computational Complexity of Semilinear Varieties
• Solving equations over small unary algebras
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• FINDING TYPE SETS IS NP-HARD
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
• The subpower membership problem for Mal'cev algebras
• Abstract Analysis of Universal Properties for tccp
• Constructive universal algebra: An introduction
• Computational complexity of some problems involving congruences on algebras

This page was built for publication: Complexity of some problems in universal algebra. Extended abstract

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4251048)