On Languages Reducible to Algorithmically Random Languages

DOI10.1137/S0097539793238140MaRDI QIDQ4327424zbMATH OpenOpenAlexFDO

Authors Ronald V. Book

Publication date 6 April 1995

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793238140

zbMATH Keywords

algorithmically random languagesindependent pair

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1759420
• On complexity classes and algorithmically random languages (extended abstract)
• On the robustness of ALMOST-$\mathcal {R}$
• An improved zero-one law for algorithmically random sequences
• scientific article; zbMATH DE number 5264766

Cited in

(16)

• An improved zero-one law for algorithmically random sequences
• Computational depth and reducibility
• On collapsing the polynomial-time hierarchy
• Optimal redundancy in computations from random oracles
• Necessary conditions for subclasses of random context languages
• Feasible reductions to Kolmogorov-Loveland stochastic sequences
• Randomness of formal languages via automatic martingales
• Limits on the Computational Power of Random Strings
• Separations by random oracles and ``almost classes for generalized reducibilities
• scientific article; zbMATH DE number 1759420 (Why is no real title available?)
• Computational depth and reducibility
• On the robustness of ALMOST-$\mathcal {R}$
• On complexity classes and algorithmically random languages (extended abstract)
• scientific article; zbMATH DE number 4187790 (Why is no real title available?)
• Local languages and the Berry-Sethi algorithm
• A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law

This page was built for publication: On Languages Reducible to Algorithmically Random Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4327424)