Approximate counting and NP search problems

Journal of Mathematical Logic 22 (3) (2022)
  Copy   BIBTEX


Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoning is the bounded arithmetic theory [math] of [E. Jeřábek, Approximate counting by hashing in bounded arithmetic, J. Symb. Log. 74(3) (2009) 829–860]. In particular, the Ramsey and weak pigeonhole search problems lie in the new class. We give a purely computational characterization of this class and show that, relative to an oracle, it does not contain the problem CPLS, a strengthening of PLS. As CPLS is provably total in the theory [math], this shows that [math] does not prove every [math] sentence which is provable in bounded arithmetic. This answers the question posed in [S. Buss, L. A. Kołodziejczyk and N. Thapen, Fragments of approximate counting, J. Symb. Log. 79(2) (2014) 496–525] and represents some progress in the program of separating the levels of the bounded arithmetic hierarchy by low-complexity sentences. Our main technical tool is an extension of the “fixing lemma” from [P. Pudlák and N. Thapen, Random resolution refutations, Comput. Complexity, 28(2) (2019) 185–239], a form of switching lemma, which we use to show that a random partial oracle from a certain distribution will, with high probability, determine an entire computation of a [math] oracle machine. The introduction to the paper is intended to make the statements and context of the results accessible to someone unfamiliar with NP search problems or with bounded arithmetic.



    Upload a copy of this work     Papers currently archived: 92,227

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Parameterized counting problems.Catherine McCartin - 2006 - Annals of Pure and Applied Logic 138 (1):147-182.
Nested PLS.Toshiyasu Arai - 2011 - Archive for Mathematical Logic 50 (3-4):395-409.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Herbrandizing search problems in Bounded Arithmetic.Jiří Hanika - 2004 - Mathematical Logic Quarterly 50 (6):577-586.
Approximate truth and dynamical theories.Peter Smith - 1998 - British Journal for the Philosophy of Science 49 (2):253-277.
Approximate Hidden Variables.M. Zisis - 2000 - Foundations of Physics 30 (7):971-1000.


Added to PP

12 (#1,090,149)

6 months
7 (#439,760)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations