Computational Complexity of the Word Problem in Modal and Heyting Algebras with a Small Number of Generators
Михаил Николаевич Рыбаков · Russian Mathematics · 2022
Abstract We consider the computational complexity of the word problem for finitely generated Heyting and modal algebras. It is shown that the word problem is PSPACE-complete if only constant modal terms or only 0-generated modal algebras are considered; similar results are obtained for two-variable terms and 2-generated Heyting algebras. It is also shown that, if an equation of positive terms is refuted in a Heyting algebra, it is refuted in a 2-generated Heyting algebra. We also consider the word problem for certain classes of modal and Heyting algebras and obtain results similar to those mentioned above for infinite families of such classes. The results are optimal in the number of generators: reduction in the number of generators leads to polynomial-time decidable word problems.