On complexity classes and algorithmically random languages
From MaRDI portal
Publication:5096791
DOI10.1007/3-540-55210-3_193zbMath1493.68148MaRDI QIDQ5096791
Jack H. Lutz, Ronald V. Book, Klaus 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
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D32: Algorithmic randomness and dimension
Cites Work
- Turing machines that take advice
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- 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
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Complexity oscillations in infinite binary sequences
- The definition of random sequences
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item