Hardness results for the subpower membership problem
From MaRDI portal
Publication:4686441
DOI10.1142/S0218196718500339zbMath1491.08012arXiv1707.08244OpenAlexW2963386822WikidataQ129895884 ScholiaQ129895884MaRDI QIDQ4686441
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
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
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)