Bi-immunity results for cheatable sets
Open Access
- 22 July 1990
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 73 (3) , 249-263
- https://doi.org/10.1016/0304-3975(90)90177-j
Abstract
No abstract availableKeywords
Funding Information
- Hertz Foundation
- National Science Foundation (CCR-8508949)
This publication has 12 references indexed in Scilit:
- On Sets Truth-Table Reducible to Sparse SetsSIAM Journal on Computing, 1988
- The complexity of optimization problemsJournal of Computer and System Sciences, 1988
- Polynomial terse setsInformation and Computation, 1988
- Oracles for Deterministic Versus Alternating ClassesSIAM Journal on Computing, 1987
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Sparse sets in NP-P: EXPTIME versus NEXPTIMEInformation and Control, 1985
- Oracle-dependent properties of the lattice of NP setsTheoretical Computer Science, 1983
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975