Погружение интуиционистской логики в ее фрагмент от двух переменных и сложность этого фрагмента.

##plugins.themes.bootstrap3.article.main##

M.N. Rybakov

Abstract

An embedding of intuitionistic propositional logic into its two-variable fragment is constructed. Using this embedding, we prove that the decision problem for two-variable fragment of intuitionistic propositional logic is PSPACE-complete.

##plugins.generic.usageStats.downloads##

##plugins.generic.usageStats.noStats##

##plugins.themes.bootstrap3.article.details##

Section
Статьи

References

Попов В.М. Погружение интуиционистского пропозиционального исчисления в его позитивны й фрагмент // Логические исследования. В ы п.8. М.: Наука, 200 3 . С. 1 5 0 -1 5 4 .

Рыбаков М.Н., Чагров Л.В. Константны е формулы в модальны х логиках: проблем а разрешения // Л огические исследования. Вып.9. М.: Наука, 2003. С. 202 -220 .

Чагров А.В. О слож ности пропозициональны х логик // С лож ностны е проблем ы м атематической логики. Калинин, 1985. С. 80 -90 .

Chagrov A., Zakharyaschev М. M odal L ogic. Oxford University Press,1997.

Garey MR., Johnson D.S Com puters and Intractability: A
Guide to the Theory o f N P -com pleteress. San Francisco, 1979. (Русский перевод: Гэри M., Джонсон Д. Вы числительные машины и труднорешаемые задачи. М.: Мир, 1982).


Halpern J. Y. The Effect of Bounding the Number of Primitive Propositions and the Depth of Nesting on the Complexity of Modal Logic // Artificial Intelligence. Vol. 75. 1995. P. 361-372.

Nishimura /. On formulas of the one variable in intuitionistic propositional calculus // The Journal of Symbolic Logic. Vol. 25. N. 1. 1960. P. 327-331.

Spaan E. Complexity of Modal Logics // PhD thesis. Department of Mathematics and Computer Science, University of Amsterdam, 1993.

Statman R. Intuitionistic propositional logic is polynomial-space complete // Theoret. Comput. Sci. Vol. 9. N. 1. 1979. P. 67-72.

Stockmeyer L. Classifying the Computational complexity of Problems // The Journal of Symbolic Logic. Vol. 52. N.l. 1987. P. 1-43. (Русский перевод: Стокмейер Л. Классификация вычислительной сложности проблем // Кибернетический сборник, вып. 26. М.: Мир, 1989. С. 20-83.)