On complexity classes and algorithmically random languages (extended abstract)
DOI10.1007/3-540-55210-3_193zbMATH Open1493.68148OpenAlexW1559067339MaRDI QIDQ5096791FDOQ5096791
Authors: Ronald V. Book, Jack H. Lutz, K. W. Wagner 
Publication date: 18 August 2022
Published in: STACS 92 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55210-3_193
Recommendations
Algorithmic randomness and dimension (03D32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Complexity oscillations in infinite binary sequences
- The definition of random sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Turing machines that take advice
- The polynomial-time hierarchy and sparse oracles
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (8)
- Polynomial-time random oracles and separating complexity classes
- On the relative complexity of some languages in \(NC^ 1\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The global power of additional queries to random oracles
- Gap-languages and log-time complexity classes
- Necessary conditions for subclasses of random context languages
- An observation on probability versus randomness with applications to complexity classes
This page was built for publication: On complexity classes and algorithmically random languages (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096791)
