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:
“Every decision is liberating, even if it leads to disaster. Otherwise, why do so many people walk upright and with open eyes into their misfortune?”
—Elias Canetti (b. 1905)
“I am always glad to think that my education was, for the most part, informal, and had not the slightest reference to a future business career. It left me free and untrammeled to approach my business problems without the limiting influence of specific training.”
—Alice Foote MacDougall (1867–1945)