Fragments of approximate counting

Journal of Symbolic Logic 79 (2):496-525 (2014)
  Copy   BIBTEX

Abstract

We study the long-standing open problem of giving$\forall {\rm{\Sigma }}_1^b$separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jeřábek’s theories for approximate counting and their subtheories. We show that the$\forall {\rm{\Sigma }}_1^b$Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole principle for FPNPfunctions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of$T_2^1$augmented with the surjective weak pigeonhole principle for polynomial time functions.

Links

PhilArchive



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

External links

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

Through your library

Similar books and articles

Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Bounded variable logics: two, three, and more. [REVIEW]Martin Otto - 1999 - Archive for Mathematical Logic 38 (4-5):235-256.
Dependence Logic with a Majority Quantifier.Arnaud Durand, Johannes Ebbing, Juha Kontinen & Heribert Vollmer - 2015 - Journal of Logic, Language and Information 24 (3):289-305.
Finger counting: The missing tool?Michael Andres, Samuel Di Luca & Mauro Pesenti - 2008 - Behavioral and Brain Sciences 31 (6):642-643.
Counting functions.Fred Johnson - 1992 - Notre Dame Journal of Formal Logic 33 (4):567-568.
Counting Things.Stanley Eveling - 2013 - Philosophical Investigations 36 (3):210-230.
I-counting is counting.Steven Savitt - 1972 - Philosophy of Science 39 (1):72-73.
Counting Pleasures and Pains, and Counting Heads.Michael Quinn - 2011 - Philosophy and Public Issues - Filosofia E Questioni Pubbliche 1 (1):21-27.
Approximate Hidden Variables.M. Zisis - 2000 - Foundations of Physics 30 (7):971-1000.

Analytics

Added to PP
2016-06-30

Downloads
38 (#422,001)

6 months
16 (#160,768)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
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.

Add more citations