Why computational complexity requires stricter martingales
From MaRDI portal
Publication:2432539
DOI10.1007/s00224-005-1135-4zbMath1103.68057MaRDI 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
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
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