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

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

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

2021

Հատոր:

56

ISSN:

2579-2784 ; e-2538-2788

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

Ալթունյան Վահագն Ն., Պետրոսյան Գարիկ Վ., Алтуняни Ваагн Н., Петросян Гарик В.

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

Որոշ տիպի նույնաբանությունների արտածման բարդությունների վերաբերյալ ; О сложности выводо внекоторого типа тавтологий

Ամփոփում:

In this paper, we investigate the proof complexities of a special type of tautologies,which are described as tautologies consisting of implications and literals. In particular,we prove that the proof of this kind of tautologies can be polynomially reduced to theproof of tautologies consisting of formulas that are described by sign-alternating trees.

Հրատարակիչ:

Изд-во НАН РА

Ձեւաչափ:

pdf

Չափեր:

էջ 65-72

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

oai:arar.sci.am:323543

Լեզու:

en

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

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