ՀՀ ԳԱԱ Զեկույցներ =Reports NAS RA

On Lower Bounds for Proofs Sizes in Frege Systems

Chubaryan, A. A. and Tamazyan, H. A. (2019) On Lower Bounds for Proofs Sizes in Frege Systems. ՀՀ ԳԱԱ Զեկույցներ, 119 (2). pp. 116-121. ISSN 0321-1339

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
261Kb

Abstract

The trivial exponential upper bounds and only Ω(n2 ) lower bound of proof sizes and Ω(n) lower bound of proof steps for tautologies with the length n were known for Frege systems. Recently the super-linear lower bound for proof steps has been obtained by first coauthor (with Armine Chubaryan and Arman Tshitoyan. Ֆրեգեի համակարգերում n երկարությամբ նույնաբանությունների համար հայտնի էին վերին ցուցչային գնահատականը և միայն Ω(n2 ) ստորին գնահատականը արտածման երկարության համար ու Ω(n) ստորին գնահատականը արտածման քայլերի համար: Վերջերս առաջին համահեղինակի (Արմինե Չուբարյանի և Արման Ճիտոյանի համահեղինակությամբ) կողմից ստացվել էր սուպեր-գծային գնահատական արտածման քայլերի համար: Для систем Фреге были известны лишь тривиальные экспоненциальные верхние оценки и только Ω(n) нижняя оценка для количества шагов и только Ω(n ) нижняя оценка для длин выводов тавтологий длины n. Недавно первым соавтором (совместно с Армине Чубарян и Арманом Читояном) была получена суперлинейная оценка для количества шагов выводов.

Item Type:Article
Additional Information:Ֆրեգեի համակարգերում արտածումների երկարությունների ստորին գնահատականների վերաբերյալ / Ա. Ա. Չուբարյան, Հ. Ա. Թամազյան: О нижних оценках длин выводов в системах Фреге / А. А. Чубарян, А. А. Тамазян.
Uncontrolled Keywords:Frege system, proof complexity, essential subformula.
Subjects:Q Science > QA Mathematics
ID Code:6436
Deposited By:NAS Reports
Deposited On:23 Aug 2019 12:34
Last Modified:26 Aug 2019 10:38

Repository Staff Only: item control page