Abstract
We consider the proof complexity of the minimal complete fragment, KS, of standard deep inference systems for propositional logic. To examine the size of proofs we employ atomic flows, diagrams that trace structural changes through a proof but ignore logical information. As results we obtain a polynomial simulation of versions of Resolution, along with some extensions. We also show that these systems, as well as bounded-depth Frege systems, cannot polynomially simulate KS, by giving polynomial-size proofs of certain variants of the propositional pigeonhole principle in KS.
Original language | English |
---|---|
Article number | 4 |
Number of pages | 27 |
Journal | Logical Methods in Computer Science |
Volume | 11 |
Issue number | 1 |
Early online date | 4 Mar 2015 |
DOIs | |
Publication status | Published - 6 Mar 2015 |
Bibliographical note
Special Issue: Selected papers of the ''Turing Centenary Conference: CiE 2012''Keywords
- Atomic flows
- Deep inference
- Graph rewriting
- Normalisation
- Proof complexity
- Proof theory
- Propositional logic
- computer science
- logic in computer science, Mathematics
- Logic
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science