ECCC-Report TR01-082https://eccc.weizmann.ac.il/report/2001/082Comments and Revisions published for TR01-082en-usMon, 26 Nov 2001 22:50:35 +0200
Paper TR01-082
| Classification of Search Problems and Their Definability in Bounded Arithmetic |
Tsuyoshi Morioka
https://eccc.weizmann.ac.il/report/2001/082We 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$.
Mon, 26 Nov 2001 22:50:35 +0200https://eccc.weizmann.ac.il/report/2001/082