On the relative proof complexity of deep inference via atomic flows

Anupam Das*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
57 Downloads (Pure)

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 languageEnglish
Article number4
Number of pages27
JournalLogical Methods in Computer Science
Volume11
Issue number1
Early online date4 Mar 2015
DOIs
Publication statusPublished - 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
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On the relative proof complexity of deep inference via atomic flows'. Together they form a unique fingerprint.

Cite this