On the robustness of ALMOST-\mathcal {R}

DOI10.1051/ITA/1996300201231MaRDI QIDQ4717048zbMATH OpenOpenAlexFDO

Authors Ronald V. Book, Elvira Mayordomo

Publication date 1 December 1996

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92528

zbMATH Keywords

ALMOST-\({\mathcal R}\)reducibility

Mathematics Subject Classification ID

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

Recommendations

• On Languages Reducible to Algorithmically Random Languages
• On complexity classes and algorithmically random languages (extended abstract)
• Probabilistic type-2 operators and ``almost-classes
• Separations by random oracles and ``almost classes for generalized reducibilities

Cites work

• Almost everywhere high nonuniform complexity
• An improved zero-one law for algorithmically random sequences
• An observation on probability versus randomness with applications to complexity classes
• scientific article; zbMATH DE number 3577197 (Why is no real title available?)
• scientific article; zbMATH DE number 3995648 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• On Languages Reducible to Algorithmically Random Languages
• Polynomial-time reducibilities and ``almost all oracle sets
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• The Complexity and Distribution of Hard Problems
• The definition of random sequences
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

Cited in

(7)

• An improved zero-one law for algorithmically random sequences
• Probabilistic type-2 operators and ``almost-classes
• On the equivalence of robustness to canonical and general elaborations
• Robustness radius for Chamberlin-Courant on restricted domains
• Dimension characterizations of complexity classes
• Limits on the Computational Power of Random Strings
• On Languages Reducible to Algorithmically Random Languages

This page was built for publication: On the robustness of ALMOST-$\mathcal {R}$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4717048)