Immunity, simplicity, probabilistic complexity classes and relativizations

DOI10.1080/00207168808803679zbMath0664.68050OpenAlexW2053484706MaRDI QIDQ3815527

Hong-zhou Li

Publication date: 1988

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168808803679

zbMATH Keywords

probabilistic complexity classesrelativizationsoraclesimmune set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Cites Work

• Relative complexity of checking and evaluating
• Immunity, Relativizations, and Nondeterminism
• On relativized nondeterministic polynomial-time bounded computations
• 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
• Completeness, Approximation and Density
• Relativized Questions Involving Probabilistic Algorithms
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Computational Complexity of Probabilistic Turing Machines
• Recursively enumerable sets and degrees

This page was built for publication: Immunity, simplicity, probabilistic complexity classes and relativizations