Journal or Publication Title:
Date of publication:
Volume:
ISSN:
Additional Information:
Ալթունյան Վահագն Ն., Պետրոսյան Գարիկ Վ., Алтуняни Ваагн Н., Петросян Гарик В.
Title:
On Proof Complexity of Some Type of Tautologies
Other title:
Որոշ տիպի նույնաբանությունների արտածման բարդությունների վերաբերյալ ; О сложности выводо внекоторого типа тавтологий
Creator:
Altunyan, Vahagn N. ; Petrosyan, Garik V.
Subject:
Mathematical cybernetics ; Computer science
Uncontrolled Keywords:
Frege systems ; Tautology ; Sign-alternating tree ; Proof complexity
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.