Polynomial Bounded Proof Complexities for Some Classes of DNF-Tautologies
DOI:
https://doi.org/10.51408/1963-0047Keywords:
Frege systems, Proof complexity, DNF, complete DNF, balanced formulasAbstract
In this paper, we present the results on Frege proof complexities of some DNFtautologies. At first we introduce the notion of complete DNFs and prove that complete DNFs are tautologies, we also show that if the proof complexities for the set of complete DNFs are polynomially bounded, then the set of DNF-tautologies D, for which the number of non-negated variables in every conjunct is O(log(D)), also has polynomially bounded proof complexities. Later we show that the set of all balanced DNF-tautologies has polynomial proof complexities..
References
S. A. Cook and A. R. Reckhow, “The relative efficiency of propositional proof systems”, Journal of Symbolic logic, vol. 44, pp. 36-50, 1979,
N. Jakob, “Narrow proofs may be spacious: Separating space and width in resolution”, SIAM Journal on Computing, vol. 39, no. 1, pp. 59-121, 2009.
A. Chubaryan and G. Petrosyan, “On some properties of several proof systems for 2- valued and 3-valued propositional logic”, Fundamentalis Scientiam, vol. 8, no. 8, pp. 70-73, 2017.
L. Strasburger, “Extension without Cut”, INRIA SaclayIle-de-France and Ecole Polytechnique, LIX, Rue de Saclay, 91128 Palaiseau Cedex, France
S. R. Buss, “Polynomial size proofs of the propositional pigeonhole principle”, Journal of Symbolic Logic, vol. 52, pp. 916-927, 1987.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
