scientific article; zbMATH DE number 3872682
From MaRDI portal
Publication:3339290
[For the entire collection see Zbl 0537.00003.] This is a survey of results concerning computational complexity of two types of problems in universal algebra: 1) the complexity of testing isomorphism in varieties of algebras; 2) the complexity of testing the first order properties of algebras. E.g. it is shown that the variety of all unary algebras with two idempotent commuting operations is isomorphism complete. A remarkable algorithm for testing whether a given groupoid is a group is sketched.
Recommendations
- Complexity of some problems in universal algebra. Extended abstract
- Universal algebra and applications in theoretical computer science
- scientific article; zbMATH DE number 3936520
- scientific article; zbMATH DE number 3915503
- scientific article; zbMATH DE number 2009986
- Computers and universal algebra: Some directions
- Computational complexity of some problems involving congruences on algebras
- Computational complexity in algebraic systems
- scientific article; zbMATH DE number 4085634
- scientific article; zbMATH DE number 3972183
Cited in
(15)- Verifying nonrigidity
- Algorithmic complexity of the problem of occurrence in commutants and members of the lower central series
- On computation complexity problems concerning relation algebras
- Computers and universal algebra: Some directions
- The isomorphism problem for varieties generated by a two-element algebra
- Complexity of the normalization of algebras
- The constraint satisfaction problem and universal algebra
- scientific article; zbMATH DE number 4217898 (Why is no real title available?)
- FINDING TYPE SETS IS NP-HARD
- Complexity of some problems in universal algebra. Extended abstract
- On the complexity of finite sorted algebras
- Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
- COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
- Security in Communication Networks
- Computational complexity of some problems involving congruences on algebras
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3339290)