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