On complexity classes and algorithmically random languages (extended abstract)

DOI10.1007/3-540-55210-3_193MaRDI QIDQ5096791zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Recommendations

• An observation on probability versus randomness with applications to complexity classes
• Power from Random Strings
• On Languages Reducible to Algorithmically Random Languages
• scientific article; zbMATH DE number 4049050
• scientific article; zbMATH DE number 3995648

Cites work

• scientific article; zbMATH DE number 4033067 (Why is no real title available?)
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3995648 (Why is no real title available?)
• Complexity oscillations in infinite binary sequences
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• The definition of random sequences
• The polynomial-time hierarchy and sparse oracles
• Turing machines that take advice
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

Cited in

(8)

• Polynomial-time random oracles and separating complexity classes
• On the relative complexity of some languages in \(NC^ 1\)
• scientific article; zbMATH DE number 1414309 (Why is no real title available?)
• scientific article; zbMATH DE number 4187790 (Why is no real title available?)
• 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)