2011; Physical and Mathematical Sciences, 45(3 (226): 3–8
Shared with The Gufo

POLYNOMIAL LENGTH PROOFS FOR SOME CLASS OF TSEITIN FORMULAS

Ashot Abajian*

Received: 2025-02-19 · Published: 2011-10-17

© 2011 The Author(s) and the original publisher.

CC BY 4.0 This work is licensed under a Creative Commons Attribution 4.0 International License.
Shared article.
Original title
POLYNOMIAL LENGTH PROOFS FOR SOME CLASS OF TSEITIN FORMULAS
Author
Ashot Abajian
Published
2011-10-17
Licence
Creative Commons Attribution 4.0 International

Abstract

In this paper the notion of quasi-hard determinative formulas is introduced and the proof complexities of such formulas are investigated. For some class of quasi-hard determinative formulas the same order lower and upper bounds for the length of proofs are obtained in several proof systems, basing on disjunctive normal forms (conjunctive normal forms).
1 / ? 100% Open in new tab Download Cite

Loading the full text…

Download Follow Updates