Ordinal notations and well-orderings in bounded arithmetic

DOI10.1016/S0168-0072(02)00066-0zbMath1015.03055MaRDI QIDQ1861331

Samuel R. Buss, Arnold Beckmann, Chris Pollett

Publication date: 16 March 2003

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

ordinal notationsbounded arithmeticfragments of Peano arithmeticwell-foundednesspolynomial local search

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Recursive ordinals and ordinal notations (03F15)

Related Items (3)

Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ The strength of extensionality. II: Weak weak set theories without infinity ⋮ A Characterisation of Definable NP Search Problems in Peano Arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How easy is local search?
• Proof theory. An introduction
• Notations for exponentiation.
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Systems of predicative analysis
• Systems of predicative analysis, II: Representations of ordinals

This page was built for publication: Ordinal notations and well-orderings in bounded arithmetic