Randomness is Hard

DOI10.1137/S0097539799360148zbMath0977.68046MaRDI QIDQ2706121

Harry Buhrman, Leen Torenvliet

Publication date: 19 March 2001

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

zbMATH Keywords

Kolmogorov complexityinteractive proofsrelativizationrandomnesscomplexity classesMerlin-ArthurArthur-MerlinCD complexityCND complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items

THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ Enumerations of the Kolmogorov function