On the robustness of ALMOST-$\mathcal {R}$

DOI10.1051/ita/1996300201231zbMath0860.68049OpenAlexW185476538MaRDI QIDQ4717048

Elvira Mayordomo, Ronald V. Book

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

reducibilityALMOST-\({\mathcal R}\)

Mathematics Subject Classification ID

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

Related Items (2)

An improved zero-one law for algorithmically random sequences ⋮ Limits on the Computational Power of Random Strings

Cites Work

• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• An improved zero-one law for algorithmically random sequences
• Almost everywhere high nonuniform complexity
• 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
• An observation on probability versus randomness with applications to complexity classes
• On Languages Reducible to Algorithmically Random Languages
• The Complexity and Distribution of Hard Problems
• The definition of random sequences
• Unnamed Item
• Unnamed Item
• Unnamed Item

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