Hardness results for the subpower membership problem

DOI10.1142/S0218196718500339zbMath1491.08012arXiv1707.08244OpenAlexW2963386822MaRDI QIDQ4686441

Jeff Shriner

Publication date: 10 October 2018

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

Full work available at URL: https://arxiv.org/abs/1707.08244

zbMATH Keywords

cube termMaltsev conditionsubpower membership problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Algebras from congruences

Cites Work

• Unnamed Item
• A finite set of functions with an EXPTIME-complete composition problem
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• The subpower membership problem for bands
• Taylor's modularity conjecture and related problems for idempotent varieties
• On \(n\)-permutable congruences
• GROWTH RATES OF ALGEBRAS, I: POINTED CUBE TERMS
• ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
• THE SUBPOWER MEMBERSHIP PROBLEM FOR MAL'CEV ALGEBRAS
• The subpower membership problem for semigroups
• Algebras Whose Congruence Lattices are Distributive.
• Distributivity and Permutability of Congruence Relations in Equational Classes of Algebras
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)