- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Partially definable forcing and bounded arithmetic
Archive for Mathematical Logic 54 (1):1-33 (2015)
Abstract
We describe a method of forcing against weak theories of arithmetic and its applications in propositional proof complexity.Other Versions
No versions found
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
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.
Analytics
Added to PP
2014-08-29
Downloads
172 (#238,456)
6 months
25 (#389,265)
2014-08-29
Downloads
172 (#238,456)
6 months
25 (#389,265)
Historical graph of downloads
Citations of this work
Typical forcings, NP search problems and an extension of a theorem of Riis.Moritz Müller - 2021 - Annals of Pure and Applied Logic 172 (4):102930.
On the consistency of circuit lower bounds for non-deterministic time.Albert Atserias, Sam Buss & Moritz Müller - 2024 - Journal of Mathematical Logic 25 (3).
On some $$\Sigma ^{B}_{0}$$-formulae generalizing counting principles over $$V^{0}$$.Eitetsu Ken - 2025 - Archive for Mathematical Logic 64 (1):117-158.
References found in this work
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
The relative efficiency of propositional proof systems.Stephen A. Cook & Robert A. Reckhow - 1979 - Journal of Symbolic Logic 44 (1):36-50.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Try MATCHA Writer if you're interested in citing directly from PhilPapers and certifying your authorship.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation