Journal or Publication Title:

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

Date of publication:

2021

Volume:

56

ISSN:

2579-2784 ; e-2538-2788

Additional Information:

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

Other title:

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

Abstract:

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.

Publisher:

Изд-во НАН РА

Format:

pdf

Extent:

էջ 65-72

Identifier:

oai:arar.sci.am:323543

Language:

en

Location of original object:

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