Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-18T00:32:51.292Z Has data issue: false hasContentIssue false

FRAGMENTS OF APPROXIMATE COUNTING

Published online by Cambridge University Press:  25 June 2014

SAMUEL R. BUSS
Affiliation:
DEPARTMENT OF MATHEMATICS, UNIVERSITY OF CALIFORNIA, SAN DIEGO, LA JOLLA, CA 92093-0112, USAE-mail:sbuss@math.ucsd.edu
LESZEK ALEKSANDER KOŁODZIEJCZYK
Affiliation:
INSTITUTE OF MATHEMATICS, UNIVERSITY OF WARSAW, BANACHA 2, 02-097 WARSZAWA, POLANDE-mail:lak@mimuw.edu.pl
NEIL THAPEN
Affiliation:
INSTITUTE OF MATHEMATICS, ACADEMY OF SCIENCES OF THE CZECH REPUBLIC, ŽITNÁ 25, 115 67 PRAHA 1, CZECH REPUBLICE-mail:thapen@math.cas.cz
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 FPNP functions. 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.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2014