Bi-immunity results for cheatable sets

DOI10.1016/0304-3975(90)90177-JzbMath0709.03032OpenAlexW2006337101MaRDI QIDQ920981

Richard Beigel

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

zbMATH Keywords

Turing machinesoracleTuring degreebi-immune setsbounded query classcheatable sets

Mathematics Subject Classification ID

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