Bounded Arithmetic, Cryptography and Complexity

Theoria 63 (3):147-167 (1997)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

2008

DOI

10.1111/j.1755-2567.1997.tb00745.x

Other Versions

reprint Buss, Samuel R. (2008) "Bounded Arithmetic, Cryptography and Complexity". Theoria 63(3):147-167

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 106,824

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Unprovability of consistency statements in fragments of bounded arithmetic.Samuel R. Buss & Aleksandar Ignjatović - 1995 - Annals of Pure and Applied Logic 74 (3):221-244.
Samuel R. Buss. Bounded arithmetic. Studies in proof theory. Lecture notes, no. 3. Bibliopolis, Naples1986, v + 221 pp. [REVIEW]A. J. Wilkie - 1991 - Journal of Symbolic Logic 56 (2):759-760.
Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ibid., vol. 52 , pp. 143–153. - Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Ibid., vol. 75 , pp. 67–77. - Domenico Zambella. Notes on polynomially bounded arithmetic. The journal of symbolic logic, vol. 61 , pp. 942–966. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
Samuel R. Buss. First-order proof theory of arithmetic. Handbook of proof theory, edited by Samuel R. Buss, Studies in logic and the foundations of mathematics, vol. 137, Elsevier, Amsterdam etc. 1998, pp. 79–147. [REVIEW]Toshiyasu Arai - 2000 - Bulletin of Symbolic Logic 6 (4):465-466.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
A model-theoretic characterization of the weak pigeonhole principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.
Samuel R. Buss. An introduction to proof theory. Handbook of proof theory, edited by Samuel R. Buss, Studies in logic and the foundations of mathematics, vol. 137, Elsevier, Amsterdam etc. 1998, p. v., pp. 1–78. [REVIEW]Toshiyasu Arai - 2000 - Bulletin of Symbolic Logic 6 (4):464-465.
An unexpected separation result in Linearly Bounded Arithmetic.Arnold Beckmann & Jan Johannsen - 2005 - Mathematical Logic Quarterly 51 (2):191-200.

Analytics

Added to PP
2010-09-13

Downloads
87 (#260,534)

6 months
4 (#1,021,603)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Feasibly constructive proofs of succinct weak circuit lower bounds.Moritz Müller & Ján Pich - 2020 - Annals of Pure and Applied Logic 171 (2):102735.
Circuit lower bounds in bounded arithmetics.Ján Pich - 2015 - Annals of Pure and Applied Logic 166 (1):29-45.

Add more citations

References found in this work

Bounded arithmetic and the polynomial hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajicek - 1995 - New York, NY, USA: Cambridge University Press.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.

Add more references