Bi-immunity results for cheatable sets
From MaRDI portal
Publication:920981
DOI10.1016/0304-3975(90)90177-JzbMath0709.03032OpenAlexW2006337101MaRDI QIDQ920981
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(90)90177-j
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)
Related Items (6)
A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ The power of frequency computation ⋮ Bounded query classes and the difference hierarchy ⋮ A proof of Beigel's cardinality conjecture ⋮ Bounded queries to SAT and the Boolean hierarchy ⋮ Strong self-reducibility precludes strong immunity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Oracle-dependent properties of the lattice of NP sets
- On helping by robust oracle machines
- Polynomial terse sets
- The complexity of optimization problems
- Bounded query classes and the difference hierarchy
- Bounded queries to SAT and the Boolean hierarchy
- A comparison of polynomial time reducibilities
- Terse, superterse, and verbose sets
- Using self-reducibilities to characterize polynomial time
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- Bi-immune sets for complexity classes
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Natural Self-Reducible Sets
- On Sets Truth-Table Reducible to Sparse Sets
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Oracles for Deterministic Versus Alternating Classes
This page was built for publication: Bi-immunity results for cheatable sets
