Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-149 | 28th October 2013 12:04

The Ordering Principle in a Fragment of Approximate Counting

RSS-Feed




TR13-149
Authors: Albert Atserias, Neil Thapen
Publication: 1st November 2013 15:49
Downloads: 2905
Keywords: 


Abstract:

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk and Thapen, 2012] and completes their program to compare the strength of Je\v{r}\'abek's bounded arithmetic theory for approximate counting with weakened versions of it.



ISSN 1433-8092 | Imprint