Decision Problems
The problem of whether a given equation holds in every Heyting algebra was shown to be decidable by S. Kripke in 1965. The precise computational complexity of the problem was established by R. Statman in 1979, who showed it was PSPACE-complete and hence at least as hard as deciding equations of Boolean algebra (shown NP-complete in 1971 by S. Cook) and conjectured to be considerably harder. The elementary or first-order theory of Heyting algebras is undecidable. It remains open whether the universal Horn theory of Heyting algebras, or word problem, is decidable. Apropos of 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. It is unknown whether free complete Heyting algebras exist except in the case of a single generator where the free Heyting algebra on one generator is trivially completable by adjoining a new top.
Read more about this topic: Heyting Algebra
Famous quotes containing the words decision and/or problems:
“The issue is privacy. Why is the decision by a woman to sleep with a man she has just met in a bar a private one, and the decision to sleep with the same man for $100 subject to criminal penalties?”
—Anna Quindlen (b. 1952)
“She has problems with separation; he has trouble with unity—problems that make themselves felt in our relationships with our children just as they do in our relations with each other. She pulls for connection; he pushes for separateness. She tends to feel shut out; he tends to feel overwhelmed and intruded upon. It’s one of the reasons why she turns so eagerly to children—especially when they’re very young.”
—Lillian Breslow Rubin (20th century)