Simplicity, Relativizations and Nondeterminism

DOI10.1137/0214012zbMath0567.68027OpenAlexW2044513355MaRDI QIDQ3683534

José L. Balcázar

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2117/102119

zbMATH Keywords

immunitycomplexity classestime boundsNPsimple setsbounded queriesrecursive oracle

Mathematics Subject Classification ID

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

Related Items (13)

On \(\Delta ^ P_ 2\)-immunity ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Simplicity, immunity, relativizations and nondeterminism ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ Immunity, simplicity, probabilistic complexity classes and relativizations ⋮ A second step toward the strong polynomial-time hierarchy ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ A uniform approach to define complexity classes ⋮ If not empty, NP-P is topologically large ⋮ Almost every set in exponential time is P-bi-immune ⋮ Resource bounded immunity and simplicity

This page was built for publication: Simplicity, Relativizations and Nondeterminism