Why computational complexity requires stricter martingales

DOI10.1007/s00224-005-1135-4zbMath1103.68057OpenAlexW2076275408MaRDI QIDQ2432539

Jack H. Lutz, John M. Hitchcock

Publication date: 25 October 2006

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-005-1135-4

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Probabilistic Algorithmic Randomness ⋮ How powerful are integer-valued martingales? ⋮ Computing absolutely normal numbers in nearly linear time ⋮ Computable randomness and betting for computable probability spaces

This page was built for publication: Why computational complexity requires stricter martingales