Geodesic
Proof complexities on a class of balanced formulas in some propositional systems
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 56 (2022) no. 2, pp. 58-65.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: balanced tautologies, elimination system, generalized splitting system, proof complexity characteristics. 
@article{UZERU_2022_56_2_a2,
     author = {A. A. Chubaryan},
     title = {Proof complexities on a class of balanced formulas in some propositional systems},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {58--65},
     publisher = {mathdoc},
     volume = {56},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2022_56_2_a2/}
}
TY  - JOUR
AU  - A. A. Chubaryan
TI  - Proof complexities on a class of balanced formulas in some propositional systems
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2022
SP  - 58
EP  - 65
VL  - 56
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2022_56_2_a2/
LA  - en
ID  - UZERU_2022_56_2_a2
ER  - 
%0 Journal Article
%A A. A. Chubaryan
%T Proof complexities on a class of balanced formulas in some propositional systems
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2022
%P 58-65
%V 56
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2022_56_2_a2/
%G en
%F UZERU_2022_56_2_a2
A. A. Chubaryan. Proof complexities on a class of balanced formulas in some propositional systems. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 56 (2022) no. 2, pp. 58-65. http://geodesic.mathdoc.fr/item/UZERU_2022_56_2_a2/

[1] S. A. Cook, R. A. Reckhow, “The Relative Efficiency of Propositional Proof Systems”, J. Symbolic Logic, 44 (1979), 36–50 | DOI | MR | Zbl

[2] L. Strasburger, “Extension without Cut”, Annals of Pure and Applied Logic, 163 (2012), 1995—2007 | DOI | MR

[3] A. A. Chubaryan, “Relative Efficiency of Some Proof Systems for Classical Propositional Logic”, Proceedings of NASA RA, 37:5 (2002), 71–84 | MR | Zbl

[4] An. Chubaryan, Arm. Chubaryan, “Bounds of Some Proof Complexity Characteristics in the System of Splitting Generalization”, Otechestv. Nauka v Epokhu Izmeneniy, 10 (2015), 11–14

[5] A. Chubaryan, S. Hovhannisyan, G. Gasparyan, “About Some Properties of a Propositional System of Generalized Splittings”, Vestnik RAU, 2 (2019), 34–42 (in Russian)

[6] A. Chubaryan, S. Hovhannisyan, G. Gasparyan, “Comparison of Two Propositional Proof Systems by Lines and by Sizes, ASL, ESM”, Logic Colloquium-2021. Book of Abstracts, Poznan, 2021, 166 pp.

[7] Y. Filmus, M. Lauria, J. Nordstrom, N. Thapen, N. Ron-Zewi, Space Complexity in Polynomial Calculus (2012 IEEE Conference on Computational Complexity (CCC)), 2012, 334–344 | MR

[8] A. Chubaryan, A. Mnatsakanyan, “On the Bounds of the Main Proof Measures in Some Propositional Proof Systems”, Scholar Journal of Phis. Math. and Stat., 1 (2014), 111–117