arnold beckmann's pages
Total Search Problems in Bounded Arithmetic and Improved Witnessing
Author: Arnold Beckmann and Jean-Jose Razafindrakoto
Title: Total Search Problems in Bounded Arithmetic and Improved Witnessing
Proceedings: Logic, Language, Information, and Computation (WoLLiC), 2017, 24th International Workshop on
Pages: 31 - 47
We define a new class of total search problems
as a subclass of Megiddo and Papadimitriou's class of total $\NP$ search
problems, in which solutions are verifiable in $\AC^0$.
We denote this class $\forall\exists\AC^0$.
We show that all total $\NP$ search problems are
equivalent wrt. $\AC^0$-many-one reductions to search problems in
$\forall\exists\AC^0$. Furthermore, we show that $\forall\exists\AC^0$
contains well-known problems such as
the Stable Marriage and the Maximal Independent Set problems.
We introduce the class of Inflationary Iteration problems in
$\forall\exists\AC^0$ and show that it characterizes the provably total $\NP$
search problems of the bounded arithmetic theory corresponding to polynomial-time.
Cook and Nguyen introduced a generic way of defining a bounded arithmetic theory
$\VC$ for complexity classes $\C$ which can be obtained using a complete problem.
For such $C$
we will define a new class $\KPT[C]$ of $\forall\exists\AC^0$ search problems
based on Student-Teacher games in which the student has computing power limited to $\AC^0$.
We prove that $\KPT[C]$ characterizes the provably total $\NP$ search
problems of the bounded arithmetic theory corresponding to $\C$.
All our characterizations are obtained via "new-style" witnessing theorems,
where reductions are provable in a theory corresponding to $\AC^0$.