PROOF COMPLEXITIES ON A CLASS OF BALANCED FORMULAS IN SOME PROPOSITIONAL SYSTEMS
DOI:
https://doi.org/10.46991/PYSU:A/2022.56.2.058Keywords:
balanced tautologies, elimination system, generalized splitting system, proof complexity characteristicsAbstract
In this paper four proof complexity characteristics for some class of balanced tautologies are investigated in two proof systems of propositional logic. One of the considered systems is based on determinative disjunctive normal form, the other on the generalization of splitting method. The optimal upper and lower bounds by logarithmic scale for all main proof complexity characteristics of considered tautologies are obtained in both systems.
References
Cook S.A., Reckhow A.R. The Relative Efficiency of Propositional Proof Systems. Journal of Symbolic Logic, 44 (1979), 36--50. https://doi.org/10.2307/2273702
Strasburger L. Extension without Cut. Annals of Pure and Applied Logic, 163 (2012), 1995--2007.
Chubaryan A. Relative Efficiency of Some Proof Systems for Classical Propositional Logic . Proceedings of NASA RA, 37 (2002); Journal of CMA (AAS), 37 (2002), 71--84.
Chubaryan An., Chubaryan Arm. Bounds of Some Proof Complexity Characteristics in the System of Splitting Generalization. Otechestv. Nauka v Epokhu Izmeneniy, 10 (2015), 11--14 (in Russian).
Chubaryan A., Hovhannisyan S., Gasparyan G. About Some Properties of a Propositional System of Generalized Splittings.
Vestnik RAU, 2 (2019), 34--42 (in Russian).
Chubaryan A., Hovhannisyan S., Gasparyan G. Comparison of Two Propositional Proof Systems by Lines and by Sizes, ASL, ESM. Logic Colloquium-2021. Book of Abstracts. Poznan (2021), 166 p.
Filmus Y., Lauria M., Nordstrom J., Thapen N., Ron-Zewi N. Space Complexity in Polynomial Calculus. 2012 IEEE Conference on Computational Complexity (CCC) (2012), 334--344.
Chubaryan A., Mnatsakanyan A. On the Bounds of the Main Proof Measures in Some Propositional Proof Systems. Scholar Journal of Phis. Math. and Stat., 1 (2014), 111--117.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.