Logical Characterizations of Bounded Query Classes I: Logspace Oracle Machines

Abstract

We consider three sub-logics of the logic (±HP)*[FO _s ] and show that these sub-logics capture the complexity classes obtained by considering logspace deterministic oracle Turing machines with oracles in NP where the number of oracle calls is unrestricted and constant, respectively; that is, the classes L^NP and L^NP[O(1)]. We conclude that if certain logics are of the same expressibility then the Polynomial Hierarchy collapses. We also exhibit some new complete problems for the complexity class L^NP via projection translations (the first to be discovered: projection translations are extremely weak logical reductions between problems) and characterize the complexity class L^NP[O(1)] as the closure of NP under a new, extremely strict truth-table reduction (which we introduce in this paper).