On the proof complexity of deep inference

Authors:
Open Access
Publisher website
Google Scholar
Abstract
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 speedup over analytic Gentzen proof systems that they polynomially simulate.
Funding Information
  • Engineering and Physical Sciences Research Council (EP/E042805/1)

This publication has 28 references indexed in Scilit: