Robust machines accept easy sets
From MaRDI portal
Publication:914369
DOI10.1016/0304-3975(90)90138-8zbMath0701.68028OpenAlexW1972556723MaRDI QIDQ914369
Hemaspaandra, Lane A., Juris Hartmanis
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)90138-8
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
A tight relationship between generic oracles and type-2 complexity theory ⋮ Unambiguous computations and locally definable acceptance types ⋮ Promise problems and access to unambiguous computation ⋮ Arthur-Merlin games in Boolean decision trees ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Separating complexity classes with tally oracles ⋮ On the topological size of p-m-complete degrees ⋮ Helping by unambiguous computation and probabilistic computation
Cites Work
- Strong nondeterministic polynomial-time reducibilities
- Qualitative relativizations of complexity classes
- Robust algorithms: a different approach to oracles
- Complexity classes without machines: on complete languages for UP
- On sparse oracles separating feasible complexity classes
- Reductions on NP and p-selective sets
- Relative complexity of checking and evaluating
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Sets with small generalized Kolmogorov complexity
- Quantitative Relativizations of Complexity Classes
- Sparse Sets, Lowness and Highness
- Complexity Measures for Public-Key Cryptosystems
- Relativized Questions Involving Probabilistic Algorithms
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Robust machines accept easy sets
