An unexpected separation result in Linearly Bounded Arithmetic

DOI10.1002/MALQ.200410019MaRDI QIDQ4666949zbMATH OpenOpenAlexFDO

Authors Arnold Beckmann, Jan Johannsen

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

Bounded Arithmeticpropositional proof system

Mathematics Subject Classification ID

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

Recommendations

• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• A second order version of S₂ⁱ and U₂¹
• Separations of theories in weak bounded arithmetic
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• scientific article; zbMATH DE number 440477

Cites work

• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• An exponential separation between regular and general resolution
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• Proof theory. An introduction

Cited in

(3)

• Separations of first and second order theories in bounded arithmetic
• scientific article; zbMATH DE number 517074 (Why is no real title available?)
• A theory for Log-Space and NLIN versus co-NLIN

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4666949)