__
TR01-082 | 24th September 2001 00:00
__

#### Classification of Search Problems and Their Definability in Bounded Arithmetic

**Abstract:**
We present a new framework for the study of search problems and their

definability in bounded arithmetic. We identify two notions of

complexity of search problems: verification complexity and

computational complexity. Notions of exact solvability and exact

reducibility are developed, and exact $\Sigma^b_i$-definability of

search problems in bounded arithmetic is introduced. We specify a new

machine model called the oblivious witness-oracle Turing machines.

<P>Based on work of Buss and Krajicek, we present a type-2 search

problem ITERATION (ITER) that characterizes the class PLS and the

exactly $\Sigma^b_1$-definable search problems of the theory T$^1_2$.

We show that the type-2 problems of Beame et. al. are not Turing

reducible to ITER. The separations of the corresponding type-2 classes

and the unprovability of certain combinatorial principles in a

relativized version of T$^1_2$ are obtained as corollaries.

<P>We also present the first characterization of the exactly

$\Sigma^b_2$-definable search problems of S$^1_2$ and T$^1_2$.