On complexity classes and algorithmically random languages

DOI10.1007/3-540-55210-3_193zbMath1493.68148OpenAlexW1559067339MaRDI 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

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: On complexity classes and algorithmically random languages