文章基本信息

标题：Classification of Search Problems and Their Definability in Bounded Arithmetic
本地全文：下载
作者：Tsuyoshi Morioka
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 i b -definability of search problems in bounded arithmetic is introduced. We specify a new machine model called the oblivious witness-oracle Turing machines.
Based on work of Buss and Krajicek, we present a type-2 search problem ITERATION (ITER) that characterizes the class PLS and the exactly 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.
We also present the first characterization of the exactly b 2 -definable search problems of S 1 2 and T 1 2 .