Proof Complexity of Hard-Determinable Balanced Tautologies in Frege Systems


  • Anahit A. Chubaryan Yerevan State University



Hard-determinable tautologies, Balanced tautologies, Frege systems, Proof complexity characteristics


Hard-determinable property and balanced property of tautologies are specified as important properties in the study of proof complexities formerly. In this paper hard-determinable and balanced properties are studied together. It is shown that some sequences of hard determinable balanced tautologies have polynomially bounded Frege proofs.


S. A. Cook and A. R. Reckhow, “The relative efficiency of propositional proof systems,” J. Symbolic Logic, vol. 44, pp. 36–50, 1979.

S. R. Aleksanyan and A. A. Chubaryan, “The polynomial bounds of proof complexity in Frege systems”, Siberian Mathematical Journal, Springer Verlag, vol. 50, no. 2, pp. 243-249, 2009.

L. Sraßburger, “Extension without cut”, Annals of Pure and Applied Logic, vol.163, pp. 1995- 2007, 2012.

A. A. Chubaryan, “Relative efficiency of a proof system in classical propositional logic,” Izv. NAN Armenii Mat., vol. 37, no. 5, pp. 71–84, 2002.

S. R. Buss, “Polynomial size proofs of the propositional pigeonhole principle,” Journal Symbolic Logic, vol. 52, pp. 916–927, 1987.




How to Cite

Chubaryan, A. A. (2022). Proof Complexity of Hard-Determinable Balanced Tautologies in Frege Systems. Mathematical Problems of Computer Science, 58, 61–66.