Robust machines accept easy sets

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

zbMATH Keywords

separationrelativizationsnondeterministic polynomial-time Turing machinesrobust oracle machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Robust machines accept easy sets