On the Proof Complexity of Deep Inference

Details On the Proof Complexity of Deep Inference On the Proof Complexity of Deep Inference

2007-09-08

arxiv.org/abs/0709.1201v3

ACM Transactions on Computational Logic 10 (2:14) 2009, pp. 1-34

Computer Science

Computational Complexity

Minor improvements over the published version. Always updated version at <http://cs.bath.ac.uk/ag/p/PrComplDI.pdf>

Scientific paper

10.1145/1462179.1462186

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.

Affiliated with

Also associated with

No associations

Rating

On the Proof Complexity of Deep Inference does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Proof Complexity of Deep Inference, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Proof Complexity of Deep Inference will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44407