PROOF COMPLEXITIES ON A CLASS OF BALANCED FORMULAS IN SOME PROPOSITIONAL SYSTEMS

Anahit A. Chubaryan

doi:10.46991/PYSU:A/2022.56.2.058

Authors

Anahit A. Chubaryan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2022.56.2.058

Keywords:

balanced tautologies, elimination system, generalized splitting system, proof complexity characteristics

Abstract

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.