A 2EXPTIME Complete Varietal Membership Problem
Marcin Kozik · SIAM Journal on Computing · 2009
We construct a finite algebra generating a variety with 2EXPTIME complete membership problem. This proves that the universal membership problem for varieties and the varietal equivalence problem are 2EXPTIME complete as well, answering the question of Bergman and Slutzki from 2000.