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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,672

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

Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Regularity in models of arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories.Leszek Aleksander Kołodziejczyk - 2006 - Journal of Symbolic Logic 71 (2):624 - 638.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
On the complexity of models of arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
The complexity of classification problems for models of arithmetic.Samuel Coskey & Roman Kossak - 2010 - Bulletin of Symbolic Logic 16 (3):345-358.
Finite reverse mathematics.Harvey Friedman - manuscript
Complexity theoretic bounded rationality and satisficing.K. V. Velupillai - 2010 - In Marisa Faggini, Concetto Paolo Vinci, Antonio Abatemarco, Rossella Aiello, F. T. Arecchi, Lucio Biggiero, Giovanna Bimonte, Sergio Bruno, Carl Chiarella, Maria Pia Di Gregorio, Giacomo Di Tollo, Simone Giansante, Jaime Gil Aluja, A. I͡U Khrennikov, Marianna Lyra, Riccardo Meucci, Guglielmo Monaco, Giancarlo Nota, Serena Sordi, Pietro Terna, Kumaraswamy Velupillai & Alessandro Vercelli (eds.), Decision Theory and Choices: A Complexity Approach. Springer Verlag Italia.
Presburger arithmetic with unary predicates is Π11 complete.Joseph Y. Halpern - 1991 - Journal of Symbolic Logic 56 (2):637 - 642.
Interpolation theorems, lower Bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Learning Theory and Descriptive Set Theory.Kevin T. Kelly - unknown

Analytics

Added to PP
2010-09-13

Downloads
77 (#214,722)

6 months
7 (#419,182)

Historical graph of downloads
How can I increase my downloads?

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 Krajíček - 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