A second step toward the strong polynomial-time hierarchy

DOI10.1007/BF02088009zbMath0665.68039MaRDI QIDQ3816982

Leen Torenvliet

Publication date: 1988

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

immunityoraclessimple setsbi-immunitystrong separation of low levels of the polynomial hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Relativization of Gurevich’s Conjectures ⋮ Resource bounded immunity and simplicity

Cites Work

• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Simplicity, immunity, relativizations and nondeterminism
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• Immunity, Relativizations, and Nondeterminism
• Relativizations comparing NP and exponential time
• Simplicity, Relativizations and Nondeterminism
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Recursive Predicates and Quantifiers

This page was built for publication: A second step toward the strong polynomial-time hierarchy