On the Proof Complexity of Deep Inference

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We obtain two results about the proof complexity of deep inference: 1) deep-inference proof systems are as powerful as Frege ones, even when both are extended with the Tseitin extension rule or with the substitution rule; 2) there are analytic deep-inference proof systems that exhibit an exponential speed-up over analytic Gentzen proof systems that they polynomially simulate.
Minor improvements over the published version. Always updated version at <http://cs.bath.ac.uk/ag/p/PrComplDI.pdf>

Keywords

Computational Complexity, Logic in Computer Science, Logic, F.2.2; F.4.1

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/227456

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0709.1201
 http://arxiv.org/abs/0709.1201
 ACM Transactions on Computational Logic 10 (2:14) 2009, pp. 1-34
 doi:10.1145/1462179.1462186

Collections

arXiv