Ամսագրի կամ հրապարակման վերնագիր:
Հրապարակման ամսաթիվ:
Հատոր:
ISSN:
Լրացուցիչ տեղեկություն:
Պետրոսյան Գարիկ Վ., Петросян Гарик В.
Վերնագիր:
Polynomial Bounded Proof Complexities for Some Classes of DNF-Tautologies
Այլ վերնագիր:
Ստեղծողը:
Խորագիր:
Mathematical cybernetics ; Computer science
Չվերահսկվող բանալի բառեր:
Frege systems ; balanced formulasbalanced formulas ; complete DNF ; DNF ; Proof complexity
Ծածկույթ:
Ամփոփում:
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. Սույն հոդվածում հետազոտվել են ԴՆՁ նույնաբանությունների որոշ դասերի արտածման բարդությունները Ֆրեգե համակարգերում: Ներմուծվել է լրիվ ԴՆՁ-ների հասկացությունը և ցույց է տրվել, որ լրիվ ԴՆՁ-ները նույնաբանություններ են: Ապացուցվել է, որ եթե լրիվ ԴՆՁ-ների բազմությունը բազմանդամորեն սահմանափակ արտածելի է, ապա բոլոր այն D ԴՆՁ-նույնաբանությունների բազմությունը, որի տարրերի յուրաքանչյուր կոնյունկտում առանց ժխտման հանդես եկող փոփոխականների քանակը O( log( jDj) ) է ևս բազմանդամորեն սահմանափակ արտածելի է: Ապացուցվել է նաև, որ բալանսավորված ԴՆՁ-նույնաբանությունների որոշակի դաս նույնպես բազմանդամորեն սահմանափակ արտածելի է: В этой статье исследованы сложности выводов в системах Фреге для некоторых классов ДНФ-тавтологий. Введено понятие полных ДНФ и доказано, что полные ДНФ являются тавтологиями и, если множество полных ДНФ имеет полиномиально ограниченные сложности выводов, то множество всех ДНФ тавтологий D в каждом конъюнкте которых число неотрицательных переменных является O( log( jDj) ) , также имеет полиномиально ограниченные сложности выводов. Далее доказано, что некоторый класс сбалансированных ДНФ тавтологий также имеет полиномиально ограниченные сложности выводов.