Notes on polynomially bounded arithmetic
Journal of Symbolic Logic 61 (3):942-966 (1996)
| Abstract | We characterize the collapse of Buss' bounded arithmetic in terms of the provable collapse of the polynomial time hierarchy. We include also some general model-theoretical investigations on fragments of bounded arithmetic | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,709 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesPavel Pudlák (2003). Parallel Strategies. Journal of Symbolic Logic 68 (4):1242-1250.
Mario Chiari & Jan Krajíček (1998). Witnessing Functions in Bounded Arithmetic and Search Problems. Journal of Symbolic Logic 63 (3):1095-1115.
Samuel R. Buss (1997). Bounded Arithmetic, Cryptography and Complexity. Theoria 63 (3):147-167.
Wolfgang Burr (2000). Fragments of Heyting Arithmetic. Journal of Symbolic Logic 65 (3):1223-1240.
Jan Krajíček (1995). Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press.
Arnold Beckmann & Samuel R. Buss (2009). Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic. Journal of Mathematical Logic 9 (01):103-138.
George Mills & Jeff Paris (1984). Regularity in Models of Arithmetic. Journal of Symbolic Logic 49 (1):272-280.
Richard Pettigrew (2009). On Interpretations of Bounded Arithmetic and Bounded Set Theory. Notre Dame Journal of Formal Logic 50 (2):141-152.
Leszek Aleksander Kołodziejczyk (2006). On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories. Journal of Symbolic Logic 71 (2):624 - 638.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads11 ( #99,650 of 550,917 )Recent downloads (6 months)1 ( #63,425 of 550,917 )How can I increase my downloads? |
My notes
Discussion
