Ordinal notations and well-orderings in bounded arithmetic
From MaRDI portal
Publication:1861331
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)
ordinal notations; bounded arithmetic; fragments of Peano arithmetic; well-foundedness; polynomial local search
03D15: Complexity of computation (including implicit computational complexity)
03F30: First-order arithmetic and fragments
03F15: Recursive ordinals and ordinal notations
Related Items
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item