An unexpected separation result in Linearly Bounded Arithmetic

DOI10.1002/MALQ.200410019zbMath1065.03039OpenAlexW2115920428MaRDI QIDQ4666949

Jan Johannsen, Arnold Beckmann

Publication date: 7 April 2005

Published in: MLQ (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200410019

zbMATH Keywords

propositional proof systemBounded Arithmetic

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• Proof theory. An introduction
• An exponential separation between regular and general resolution
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Unnamed Item

This page was built for publication: An unexpected separation result in Linearly Bounded Arithmetic