Open AccessPolynomial Bounded Proof Complexities for Some Classes of DNF-Tautologies
Author(s) -
Garik Petrosyan
Publication year - 2020
Publication title -
mathematical problems of computer science
Language(s) - English
Resource type - Journals
eISSN - 2738-2788
pISSN - 2579-2784
DOI - 10.51408/1963-0047
Subject(s) - bounded function , mathematics , set (abstract data type) , direct proof , discrete mathematics , combinatorics , polynomial , computer science , mathematical analysis , programming language
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..