Object

Title: Proof Complexity of Hard-Determinable Balanced Tautologies in Frege Systems

Ստեղծողը:

Chubaryan, Anahit A.

Տեսակ:

Հոդված

Ամսագրի կամ հրապարակման վերնագիր:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Հրապարակման ամսաթիվ:

2022

Համար:

58

ISSN:

2579-2784 ; e-2538-2788

Պաշտոնական URL:


Լրացուցիչ տեղեկություն:

Չուբարյան Անահիտ Ա., Чубарян Анаит А.

Այլ վերնագիր:

Դժվար-որոշելի բալանսավորված նույնաբանությունների արտածումների բարդությունները Ֆրեգեի համակարգերում ; Сложности выводов трудно-определяемых балансированныхформул в системах Фреге

Համատեղ հեղինակները:

Yerevan State University (YSU)

Ծածկույթ:

61-66

Ամփոփում:

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.
Նախկինում նույնաբանությունների դժվար-որոշելիության հատկությունը և բալանսավորված լինելու հատկությունը առանձնացվել էին որպես կարևոր հատկություններ արտածումների բարդությունների ուսումնասիրություններում: Այս հոդվածոմ դժվար-որոշելիության և բալանսավորված լինելու հատկությունները ուսումնասիրվում են համատեղ: Ապացուցվել է, որ դժվար-որոշելի բալանսավորված նույնաբանությունների մեկ դասի համար արտածումները Ֆրեգեի համակարգերում բազմանդամորեն սահմանափակ են:
Ранее свойство трудно-определяемости и свойство балансированности тавтологий были выдлены как важные свойства в исследованиях сложностей выводов. В настоящей статье свойства трудно-определяемости и балансированности изучаются совместно. Доказана полиномиальная ограниченность выводов в системах Фреге для некоторого класса трудно-определяемых балансированных формул.


Հրատարակիչ:

Изд-во НАН РА

Ձևաչափ:

pdf

Նույնացուցիչ:

oai:arar.sci.am:345942

Բնօրինակի գտնվելու վայրը:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան

Object collections:

Last modified:

Dec 8, 2023

In our library since:

Feb 27, 2023

Number of object content hits:

18

All available object's versions:

https://arar.sci.am/publication/375151

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

This page uses 'cookies'. More information