[Proof Complexity] New preprint

[Jean Jose Razafindrakoto]

Dear Colleagues,

Arnold Beckmann and I have a preprint titled

“Total Search Problems in Bounded Arithmetic and Improved Witnessing.”

which is now available at our webpages:

http://www.cs.swan.ac.uk/~csarnold/publ/index.php
http://cs.swan.ac.uk/~csjjr/

Please find below the abstract. Comments, suggestions and corrections are
appreciated!

Best regards,

Jean Jose Razafindrakoto

*******************************************************************************************************

Abstract:

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 AC0. We denote this class \forall\exists\AC0. We show that
all total NP search problems are equivalent, wrt. AC0-many-one reductions,
to search problems in \forall\exists\AC0. Furthermore, we show that
\forall\exists\AC0 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\AC0 and show that it
characterises the provably total NP search problems of the bounded
arithmetic theories 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\AC0 search
problems based on Student-Teacher games in which the student has computing
power limited to AC0. 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 AC0.


-- 
Jean Jose