User Settings
Article10.3233/fi-1993-18106

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

Iain A. Stewart-1993-01-01-Fundamenta Informaticae
24

TL;DRAbstract

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.

Chat with Paper

AI Agents for this Paper

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.

Keywords

OracleTuring machineTime hierarchy theoremComputer scienceComplexity classPolynomial hierarchyClass (philosophy)Theoretical computer science

Chat

Click to start Chat