Preprint:

    Samuel R. Buss, Leszek Aleksander Kołodziejczyk, and Neil Thapen
    "Fragments of Approximate Counting"
    Journal of Symbolic Logic 49 (2014) 496-525.

    Download manuscript: PDF.

Abstract:  We study the long-standing open problem of giving $\forall \Sigma^b_1$ 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 Jerabek's theories for approximate counting and their subtheories. We show that the $\forall \Sigma^b_1$ 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 $FP^{NP}$ functions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of $T^1_2$ augmented with the surjective weak pigeonhole principle for polynomial time functions.

Back to Sam Buss's publications page.