What can be efficiently reduced to the Kolmogorov-random strings?

DOI10.1016/j.apal.2005.06.003zbMath1088.03037OpenAlexW1990663377MaRDI QIDQ2576937

Eric W. Allender, Michal Koucký, Harry Buhrman

Publication date: 29 December 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2005.06.003

zbMATH Keywords

Kolmogorov complexitycomplexity classespolynomial-time reducibilityuniversal machineresource-bounded reducibilities

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

A MINIMAL SET LOW FOR SPEED ⋮ Randomness, Computation and Mathematics ⋮ On Low for Speed Oracles ⋮ Some games on Turing machines and power from random strings ⋮ The Complexity of Complexity ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Limits on the Computational Power of Random Strings ⋮ On low for speed oracles ⋮ On the computational power of random strings

Cites Work

• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Proof verification and the hardness of approximation problems
• Algorithmic Randomness and Complexity
• Probabilistic checking of proofs
• Optimal enumerations and optimal gödel numberings
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the complexity of random strings
• Completeness, the Recursion Theorem, and Effectively Simple Sets
• Kolmogorov entropy in the context of computability theory