On \(\Delta ^ P_ 2\)-immunity

DOI10.1016/0020-0190(86)90125-0zbMath0609.68036OpenAlexW83081171MaRDI QIDQ1087016

José L. Balcázar

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90125-0

zbMATH Keywords

polynomial-time hierarchyrelativizationcomplexity classesimmune setsrecursive oracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• A uniform approach to obtain diagonal sets in complexity classes
• Complete sets and the polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Relativized polynomial hierarchies extending two levels
• Immunity, Relativizations, and Nondeterminism
• Simplicity, Relativizations and Nondeterminism

This page was built for publication: On \(\Delta ^ P_ 2\)-immunity