Partially definable forcing and bounded arithmetic

&
Archive for Mathematical Logic 54 (1):1-33 (2015)
  Copy   BIBTEX

Abstract

We describe a method of forcing against weak theories of arithmetic and its applications in propositional proof complexity.

Categories

Keywords

Reprint years

DOI

10.1007/s00153-014-0398-3

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,907

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

A maximal bounded forcing axiom.David Asperó - 2002 - Journal of Symbolic Logic 67 (1):130-142.
Strict $${\Pi^1_1}$$ -reflection in bounded arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.
Proper forcing, cardinal arithmetic, and uncountable linear orders.Justin Tatch Moore - 2005 - Bulletin of Symbolic Logic 11 (1):51-60.
NP Search Problems in Low Fragments of Bounded Arithmetic.Jan Krajíček, Alan Skelley & Neil Thapen - 2007 - Journal of Symbolic Logic 72 (2):649 - 672.
A note on sharply bounded arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.
Provably recursive functions of constructive and relatively constructive theories.Morteza Moniri - 2010 - Archive for Mathematical Logic 49 (3):291-300.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Forcing in Finite Structures.Domenico Zambella - 1997 - Mathematical Logic Quarterly 43 (3):401-412.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
Separations of first and second order theories in bounded arithmetic.Masahiro Yasumoto - 2005 - Archive for Mathematical Logic 44 (6):685-688.
Projective Well-Orderings and Bounded Forcing Axioms.Andrés Eduardo Caicedo - 2005 - Journal of Symbolic Logic 70 (2):557 - 572.

Analytics

Added to PP
2014-08-29

Downloads
34 (#483,159)

6 months
12 (#241,801)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

[Omnibus Review].Kenneth Kunen - 1969 - Journal of Symbolic Logic 34 (3):515-516.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.

View all 22 references / Add more references