Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machine
Iain A. Stewart · Fundamenta Informaticae · 1993
This paper continues an investigation into the expressibility of the logic (±HP)*[FOS]. In particular, we show that the logic (±HP)*[FOS] has the same expressibility as its sub-logic (±HP)1[FOS] which is known to capture the complexity class LNP (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 PNP collapses.