An International Publisher for Academic and Scientific Journals
Author Login
Scholars Journal of Physics, Mathematics and Statistics | Volume-1 | Issue-02
On the bounds for the main proof measures in some propositional proof systems
Anahit Chubaryan, Armen Mnatsakanyan
Published: Nov. 27, 2014 |
80
82
DOI: 10.36347/sjpms
Pages: 111-117
Downloads
Abstract
Various proof complexity characteristics are investigated in three propositional proof systems, based on
determinative disjunctive normal forms. The comparative analysis for size, time, space, width of proofs is given. For
some formula family we obtain in our systems simultaneously bounds for different proof complexity measures
(asymptotically the same upper and lower bounds for each measures). These results can be generalized for the other
formulas and for the other systems also..
Key Words: Determinative conjunct, determinative disjunctive normal form, elimination rule, size, time, space, width of
proofs