On the Proof Complexity of Deep Inference
| dc.creator | Bruscoli, Paola | |
| dc.creator | Guglielmi, Alessio | |
| dc.date | 2007-09-08 | |
| dc.date | 2009-04-19 | |
| dc.date.accessioned | 2026-07-07T13:05:20Z | |
| dc.date.available | 2026-07-07T13:05:20Z | |
| dc.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. | |
| dc.description | Minor improvements over the published version. Always updated version at <http://cs.bath.ac.uk/ag/p/PrComplDI.pdf> | |
| dc.identifier | https://arxiv.org/abs/0709.1201 | |
| dc.identifier | http://arxiv.org/abs/0709.1201 | |
| dc.identifier | ACM Transactions on Computational Logic 10 (2:14) 2009, pp. 1-34 | |
| dc.identifier | doi:10.1145/1462179.1462186 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/227456 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | Logic | |
| dc.subject | F.2.2; F.4.1 | |
| dc.title | On the Proof Complexity of Deep Inference | |
| dc.type | text |