Editing Heyting algebra (section)

==Decision problems==
The problem of whether a given equation holds in every Heyting algebra was shown to be decidable by [[Saul Kripke]] in 1965.<ref name="Kripke63" /> The precise [[Computational complexity theory|computational complexity]] of the problem was established by [[Richard Statman]] in 1979, who showed it was [[PSPACE-complete]]<ref>{{cite journal | last1 = Statman | first1 = R. | year = 1979 | title = Intuitionistic propositional logic is polynomial-space complete | journal = Theoretical Comput. Sci. | volume = 9 | pages = 67–72 | doi=10.1016/0304-3975(79)90006-9| hdl = 2027.42/23534 | hdl-access = free }}</ref> and hence at least as hard as [[Boolean satisfiability problem|deciding equations of Boolean algebra]] (shown coNP-complete in 1971 by [[Stephen Cook]])<ref name="Cook71">{{Cite conference|last = Cook  | first = S.A. | author-link = Stephen A. Cook  | title = The complexity of theorem proving procedures
 | book-title = Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York | year = 1971 | pages = 151–158 | doi = 10.1145/800157.805047| doi-access = free}}</ref> and conjectured to be considerably harder.  The elementary or first-order theory of Heyting algebras is undecidable.<ref>{{cite journal | last1 = Grzegorczyk | first1 = Andrzej | author-link = Andrzej Grzegorczyk | year = 1951 | title = Undecidability of some topological theories | url =https://www.impan.pl/shop/publication/transaction/download/product/93826?download.pdf | journal = Fundamenta Mathematicae | volume = 38 | pages = 137–52 | doi = 10.4064/fm-38-1-137-152 }}</ref> It remains open whether the [[universal Horn theory]] of Heyting algebras, or [[word problem (mathematics)|word problem]], is decidable.<ref>Peter T. Johnstone, ''Stone Spaces'', (1982) Cambridge University Press, Cambridge, {{ISBN|0-521-23893-5}}. ''(See paragraph 4.11)''</ref>  Regarding the word problem it is known that Heyting algebras are not locally finite (no Heyting algebra generated by a finite nonempty set is finite), in contrast to Boolean algebras, which are locally finite and whose word problem is decidable.