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

DOI10.1007/978-3-319-74772-9_9MaRDI QIDQ4586419zbMATH OpenOpenAlexFDO

Authors George F. McNulty

Publication date 13 September 2018

Published in Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-74772-9_9

zbMATH Keywords

finite algebra decision problemsminimal variety of algebrasNP-hardness

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Varieties (08B99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Computing generating sets of minimal size in finite algebras
• On the complexity of deciding homomorphism-homogeneity for finite algebras
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• scientific article; zbMATH DE number 1507184
• Computing the structure of finite algebras
• A Complete Characterization of the Algebras of Minimal Bilinear Complexity
• On the complexity of counting components of algebraic varieties
• scientific article; zbMATH DE number 922712
• scientific article; zbMATH DE number 3977205

Cites work

• A 2EXPTIME complete varietal membership problem
• A Characterization of Minimal Locally Finite Varieties
• Alternation
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
• Computational complexity of some problems involving congruences on algebras
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• Finite bases for flat graph algebras
• Full duality among graph algebras and flat graph algebras
• scientific article; zbMATH DE number 3122417 (Why is no real title available?)
• scientific article; zbMATH DE number 3809626 (Why is no real title available?)
• scientific article; zbMATH DE number 515651 (Why is no real title available?)
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Minimal, locally-finite varieties that are not finitely axiomatizable
• On Comparison of Finite Algebras
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• The decidability of the affine completeness generation problem.
• The First Order Theory of N-Colorable Graphs
• THE RESIDUAL BOUND OF A FINITE ALGEBRA IS NOT COMPUTABLE
• THE RESIDUAL BOUNDS OF FINITE ALGEBRAS

Cited in

(1)

• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)

This page was built for publication: The computational complexity of deciding whether a finite algebra generates a minimal variety

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