2 results
7 - Further Proof Systems
- from Part I - Basic Concepts
-
- Book:
- Proof Complexity
- Published online:
- 25 March 2019
- Print publication:
- 28 March 2019, pp 134-162
-
- Chapter
- Export citation
FRAGMENTS OF APPROXIMATE COUNTING
-
- Journal:
- The Journal of Symbolic Logic / Volume 79 / Issue 2 / June 2014
- Published online by Cambridge University Press:
- 25 June 2014, pp. 496-525
- Print publication:
- June 2014
-
- Article
- Export citation
-
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.
