Switch to: Citations

Add references

You must login to add references.
  1. Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
    The bounded arithmetic theory S2 is finitely axiomatized if and only if the polynomial hierarchy provably collapses. If T2i equals S2i + 1 then T2i is equal to S2 and proves that the polynomial time hierarchy collapses to ∑i + 3p, and, in fact, to the Boolean hierarchy over ∑i + 2p and to ∑i + 1p/poly.
    Download  
     
    Export citation  
     
    Bookmark   20 citations  
  • [Symbol] o-categoricity over a predicate.Anand Pillay - 1983 - Notre Dame Journal of Formal Logic 24:527-536.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • (1 other version)Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
    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.
    Download  
     
    Export citation  
     
    Bookmark   39 citations  
  • Classification theory over a predicate. I.Anand Pillay & Saharon Shelah - 1985 - Notre Dame Journal of Formal Logic 26 (4):361-376.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Provability of the pigeonhole principle and the existence of infinitely many primes.J. B. Paris, A. J. Wilkie & A. R. Woods - 1988 - Journal of Symbolic Logic 53 (4):1235-1244.
    Download  
     
    Export citation  
     
    Bookmark   28 citations  
  • (1 other version)Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
    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.
    Download  
     
    Export citation  
     
    Bookmark   28 citations