Structures interpretable in models of bounded arithmetic

DOI10.1016/j.apal.2005.04.005zbMath1083.03041OpenAlexW1993827888MaRDI QIDQ2570136

Neil Thapen

Publication date: 26 October 2005

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

Full work available at URL: https://doi.org/10.1016/j.apal.2005.04.005

zbMATH Keywords

bounded arithmeticmodels of arithmeticarithmetic with a topWeak Pigeonhole Principle

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Nonstandard models of arithmetic (03H15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Models of arithmetic and set theory (03C62)

Related Items (4)

FRAGMENTS OF APPROXIMATE COUNTING ⋮ The polynomial and linear hierarchies in models where the weak pigeonhole principle fails ⋮ Approximate counting in bounded arithmetic ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A uniform approach to define complexity classes
• A model-theoretic characterization of the weak pigeonhole principle
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Algorithms for Black-Box Fields and their Application to Cryptography
• Provability of the pigeonhole principle and the existence of infinitely many primes
• A new proof of the weak pigeonhole principle

This page was built for publication: Structures interpretable in models of bounded arithmetic