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

Article type: Research Article

Authors: Stewart, Iain A.

Affiliations: Computing Laboratory, Univ. Newcastle upon Tyne, Claremont Tower, Claremont Road, Newcastle upon Tyne, NE1 7RU, U.K.

Abstract: 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.

DOI: 10.3233/FI-1993-18106

Journal: Fundamenta Informaticae, vol. 18, no. 1, pp. 93-105, 1993