The Ordering Principle in a Fragment of Approximate Counting

descriptionPublicationkeyboard_double_arrow_right Article 01 Aug 2014 Spain, Czech Republic English Publisher:Association for Computing Machinery (ACM)Journal:ACM Transactions on Computational Logic, volume 15, pages 1-11 (issn: 1529-3785, eissn: 1557-945X,

Copyright policy )

Authors: Atserias, Albert; Thapen, Neil;

doi: 10.1145/2629555

handle: 2117/28288 , 11104/0241058

The Ordering Principle in a Fragment of Approximate Counting

- Summary
- Subjects
- Metrics

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 T 1 2 . This answers an open question raised in Buss et al. [2012] and completes their program to compare the strength of Jeřábek's bounded arithmetic theory for approximate counting with weakened versions of it.

Countries

Spain, Czech Republic

Related Organizations

Universitat Polite`cnica de Catalunya
Spain
Czech Academy of Sciences
Czech Republic
Universitat Politècnica de Catalunya
Spain
Academy of Sciences Library
Czech Republic

Keywords

Complexity of proofs, Complexity of computation (including implicit computational complexity), First-order arithmetic and fragments, computational complexity, bounded arithmetic, Polynomial local search, Weak Pigeonhole Principle, :Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat [Àrees temàtiques de la UPC], Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat, Computational complexity, propositional proof complexity, Bounded arithmetic, Theory, Propositional proof complexity, Complexitat computacional, polynomial local search, Algorithms

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	5
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average