Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machine

Abstract

This paper continues an investigation into the expressibility of the logic (±HP)*[FO _S ]. In particular, we show that the logic (±HP)*[FO _S ] has the same expressibility as its sub-logic (±HP)¹[FO _S ] which is known to capture the complexity class L^NP (this class being those sets of strings accepted by some logspace deterministic oracle Turing machine with an oracle in NP). We consequently show that a naturally defined hierarchy within P^NP collapses.