Proof Complexity of Hard-Determinable Balanced Tautologies in Frege Systems
DOI:
https://doi.org/10.51408/1963-0093Keywords:
Hard-determinable tautologies, Balanced tautologies, Frege systems, Proof complexity characteristicsAbstract
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.
References
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Anahit A. Chubaryan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
