COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA

DOI10.1142/S0218196702001127MaRDI QIDQ4791998zbMATH OpenDBLPWikidataFDO

Authors Clifford Bergman, Giora Slutzki

Publication date 9 February 2003

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subalgebras, congruence relations (08A30)

Recommendations

• Computational complexity of some problems involving congruences on algebras
• scientific article; zbMATH DE number 1304317
• Computers and universal algebra: Some directions
• scientific article; zbMATH DE number 3880117
• scientific article; zbMATH DE number 3872682

Cites work

• An algorithm for determining \(\Phi(L)\) in finite distributive lattices
• Bounded Query Classes
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• Complete problems for deterministic polynomial time
• Complete sets and the polynomial-time hierarchy
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Deciding Frattini is NP-complete
• Irreducible elements and uniquely generated algebras
• Maximal sublattices of finite distributive lattices
• Moufang loops of class 2 and cubic forms
• On truth-table reducibility to SAT
• The strong exponential hierarchy collapses

Cited in

(7)

• On the Complexity of Computing Generators of Closed Sets
• Non-generators in complete lattices and semilattices
• scientific article; zbMATH DE number 3880117 (Why is no real title available?)
• Algebraic dependence in generating functions and expansion complexity
• Computing generating sets of minimal size in finite algebras
• Mathematical Foundations of Computer Science 2004
• The computational complexity of deciding whether a finite algebra generates a minimal variety

This page was built for publication: COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA

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