Չուբարյան Անահիտ Ա., Чубарян Анаит А.
Դժվար-որոշելի բալանսավորված նույնաբանությունների արտածումների բարդությունները Ֆրեգեի համակարգերում ; Сложности выводов трудно-определяемых балансированныхформул в системах Фреге
Yerevan State University (YSU)
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.
Նախկինում նույնաբանությունների դժվար-որոշելիության հատկությունը և բալանսավորված լինելու հատկությունը առանձնացվել էին որպես կարևոր հատկություններ արտածումների բարդությունների ուսումնասիրություններում: Այս հոդվածոմ դժվար-որոշելիության և բալանսավորված լինելու հատկությունները ուսումնասիրվում են համատեղ: Ապացուցվել է, որ դժվար-որոշելի բալանսավորված նույնաբանությունների մեկ դասի համար արտածումները Ֆրեգեի համակարգերում բազմանդամորեն սահմանափակ են:
Ранее свойство трудно-определяемости и свойство балансированности тавтологий были выдлены как важные свойства в исследованиях сложностей выводов. В настоящей статье свойства трудно-определяемости и балансированности изучаются совместно. Доказана полиномиальная ограниченность выводов в системах Фреге для некоторого класса трудно-определяемых балансированных формул.
oai:arar.sci.am:345942
ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան
Dec 8, 2023
Feb 27, 2023
17
https://arar.sci.am/publication/375151
Հրատարակութեան անունը | Թուական |
---|---|
Chubaryan, Anahit A., Proof Complexity of Hard-Determinable Balanced Tautologies in Frege Systems | Dec 8, 2023 |
Sargsyan, Shushanik A. Edita G. Gzoyan
Apinyan, Levon A. Chubaryan, Anahit A.