Robust machines accept easy sets (Q914369): Difference between revisions

@@ Property / author @@
+Juris Hartmanis
@@ Property / author: Juris Hartmanis / rank @@
+Normal rank
@@ Property / author @@
+Hemaspaandra, Lane A.
@@ Property / author: Hemaspaandra, Lane A. / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(90)90138-8
+Normal rank
@@ Property / OpenAlex ID @@
+W1972556723
@@ Property / OpenAlex ID: W1972556723 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+Sets with small generalized Kolmogorov complexity
@@ Property / cites work: Sets with small generalized Kolmogorov complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse Sets, Lowness and Highness
@@ Property / cites work: Sparse Sets, Lowness and Highness / rank @@
+Normal rank
@@ Property / cites work @@
+Quantitative Relativizations of Complexity Classes
+Normal rank
@@ Property / cites work @@
+Qualitative relativizations of complexity classes
@@ Property / cites work: Qualitative relativizations of complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity Measures for Public-Key Cryptosystems
@@ Property / cites work: Complexity Measures for Public-Key Cryptosystems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3802608
@@ Property / cites work: Q3802608 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity classes without machines: on complete languages for UP
+Normal rank
@@ Property / cites work @@
+On sparse oracles separating feasible complexity classes
+Normal rank
@@ Property / cites work @@
+Q3805899
@@ Property / cites work: Q3805899 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3356300
@@ Property / cites work: Q3356300 / rank @@
+Normal rank
@@ Property / cites work @@
+Strong nondeterministic polynomial-time reducibilities
+Normal rank
@@ Property / cites work @@
+Relativized Questions Involving Probabilistic Algorithms
+Normal rank
@@ Property / cites work @@
+Robust algorithms: a different approach to oracles
+Normal rank
@@ Property / cites work @@
+Complexity of Presburger arithmetic with fixed quantifier dimension
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+Reductions on NP and p-selective sets
@@ Property / cites work: Reductions on NP and p-selective sets / rank @@
+Normal rank
@@ Property / cites work @@
+Relative complexity of checking and evaluating
@@ Property / cites work: Relative complexity of checking and evaluating / rank @@
+Normal rank