A 2EXPTIME Complete Varietal Membership Problem

DOI10.1137/070680801zbMath1192.68369OpenAlexW2083563264MaRDI QIDQ3654383

Marcin Kozik

Publication date: 6 January 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/051a5a00d045f98ed6d7dd1d53351c192ad5d6ba

zbMATH Keywords

computational complexityalternating Turing machinehyperexponential timevarietal membership problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices of varieties (08B15) Abstract data types; algebraic specification (68Q65) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (5)

Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting) ⋮ Complexity of the identity checking problem for finite semigroups. ⋮ The computational complexity of deciding whether a finite algebra generates a minimal variety ⋮ A minimal nonfinitely based semigroup whose variety is polynomially recognizable. ⋮ Low Growth Equational Complexity

This page was built for publication: A 2EXPTIME Complete Varietal Membership Problem