Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style


Jiri Hanika

Search Problems and Bounded Arithmetic


Faculty of Mathematics and Physics
Charles University, Prague


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

ISSN 1433-8092 | Imprint