Object

Title: On Proof Complexity of Some Type of Tautologies

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

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=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

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

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

Object collections:

Last modified:

Dec 8, 2023

In our library since:

Jul 15, 2022

Number of object content hits:

22

All available object's versions:

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

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

This page uses 'cookies'. More information