The question of the minimum complexity of derivation of a given formula in classical propositional calculus is considered in this article and it is proved that estimates of complexity may vary considerably among the various forms of propositional calculus. The forms of propositional calculus used in the present article are somewhat unusual, † but the results obtained for them can, in principle, be extended to the usual forms of propositional calculus.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- On the Complexity of Derivation in Propositional Calculus
G. S. Tseitin
- Springer Berlin Heidelberg