Robust machines accept easy sets
type: Item
instance of: scholarly article
title: Robust machines accept easy sets
zbMATH Open document ID: 0701.68028
DOI: 10.1016/0304-3975(90)90138-8
published in: Theoretical Computer Science
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4149543
zbMATH Keywords: separation
zbMATH Keywords: robust oracle machines
zbMATH Keywords: nondeterministic polynomial-time Turing machines
zbMATH Keywords: relativizations
author: J. Hartmanis
author: Lane A. Hemaspaandra
MaRDI profile type: Publication
full work available at URL: 0304-3975(90)90138-8
OpenAlex ID: W1972556723
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Sets with small generalized Kolmogorov complexity
cites work: Sparse Sets, Lowness and Highness
cites work: Quantitative Relativizations of Complexity Classes
cites work: Qualitative relativizations of complexity classes
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Q3802608
cites work: Complexity classes without machines: on complete languages for UP
cites work: On sparse oracles separating feasible complexity classes
cites work: Q3805899
cites work: Q3356300
cites work: Strong nondeterministic polynomial-time reducibilities
cites work: Relativized Questions Involving Probabilistic Algorithms
cites work: Robust algorithms: a different approach to oracles
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: Reductions on NP and p-selective sets
cites work: Relative complexity of checking and evaluating
description: scientific article; zbMATH DE number 4149543