### Jiri Hanika

## Search Problems and Bounded Arithmetic

Faculty of Mathematics and Physics
Charles University, Prague
**Abstract**

We study search problems and reducibilities between them with known or
potential relevance to bounded arithmetic theories. Our primary objective
is to understand the sets of low complexity consequences (esp. *Sigma_1^b*
or *Sigma_2^b*) of theories *S^i_2* and *T^i_2* for a small *i*, ideally in
a rather strong sense of characterization; or, at least in the standard
sense of axiomatization. We also strive for maximum combinatorial
simplicity of the characterizations and axiomatizations eventually
sufficient to prove conjectured separation results. To this end two
techniques based on the Herbrand's theorem are developed. They
characterize/axiomatize *Sigma_1^b*-consequences of *Sigma_2^b*-definable
search problems, while the method based on the more involved concept of
characterization is easier and gives more transparent results. This method
yields new proofs of Buss' witnessing theorem and of the relation between
*PLS* and *Sigma_1^b(T^1_2)*, and also an axiomatization of
*Sigma_1^b(T^2_2)*. We also investigate the relations among known search
problems such as *GI*, *MIN* and *GLS* and some of their variants.

**Table of Contents**

1. Preliminary Computational Complexity
*1.1. Data Representation
*

*1.2. Computational Model Details
*

*1.3. Computational Model Notation
*

*
**2. Preliminary Bounded Arithmetic
**2.1. Basics
*

*2.2. Language
*

*2.3. Bounded Quantifier Complexity
*

*2.4. Theories
*

*2.5. Fractions
*

*2.6. Sequence Coding
*

*
**3. Search Problems
**3.1. Basic Framework
*

*3.2. Reducibilities
*

*3.3. Promise and No Promise
*

*3.4. Turing versus Many-One
*

*3.5. Relativized Framework
*

*
**4. Characterizations
**4.1. Many-One Based Characterizations
*

*4.2. Consequence Based Characterizations
*

*4.3. So What Is the Question?
*

*4.3.1 $S^j_2$ or $T^j_2$?
*

*4.3.2 $S^j_2$ or $S^j_2(\alpha )$?
*

*4.3.3 Many-One or Consequence?
*

*4.3.4 $\Sigma _i^b$ or $\Pi _i^b$?
*

*4.3.5 An Illustrative Summary
*

*
**5. The Diagonal
**5.1. General Background: Buss' Theorem
*

*5.2. Function Minimization
*

*
**6. The Superdiagonal
**6.1. General Background: Bounded Queries
*

*6.2. Sharp Function Minimization
*

*
**7. The Subdiagonal
**7.1. Polynomial Local Search
*

*7.2. Generalized Local Search
*

*7.3. Minimization
*

*7.4. Generalized Iteration
*

*
**8. Star Herbrandization
**8.1. General Construction
*

*8.2. Applications
*

*
**9. Dagger Herbrandization
**9.1. General Construction
*

*9.2. Applications
*

*
**A. Appendix: Three Myths About Function Problems
*

*
*
**Number of pages:** 83