Robust machines accept easy sets
From MaRDI portal
Recommendations
Cites work
- Complexity classes without machines: on complete languages for UP
- Complexity Measures for Public-Key Cryptosystems
- Complexity of Presburger arithmetic with fixed quantifier dimension
- scientific article; zbMATH DE number 4208065 (Why is no real title available?)
- scientific article; zbMATH DE number 4070309 (Why is no real title available?)
- scientific article; zbMATH DE number 4074483 (Why is no real title available?)
- On sparse oracles separating feasible complexity classes
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Qualitative relativizations of complexity classes
- Quantitative Relativizations of Complexity Classes
- Reductions on NP and p-selective sets
- Relative complexity of checking and evaluating
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized Questions Involving Probabilistic Algorithms
- Robust algorithms: a different approach to oracles
- Sets with small generalized Kolmogorov complexity
- Sparse Sets, Lowness and Highness
- Strong nondeterministic polynomial-time reducibilities
Cited in
(10)- Unambiguous computations and locally definable acceptance types
- Separating complexity classes with tally oracles
- A tight relationship between generic oracles and type-2 complexity theory
- Arthur-Merlin games in Boolean decision trees
- scientific article; zbMATH DE number 4172379 (Why is no real title available?)
- scientific article; zbMATH DE number 3883614 (Why is no real title available?)
- Fault-tolerance and complexity (extended abstract)
- Promise problems and access to unambiguous computation
- On the topological size of p-m-complete degrees
- Helping by unambiguous computation and probabilistic computation
This page was built for publication: Robust machines accept easy sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q914369)
