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 complexity; interactive proofs; relativization; randomness; complexity classes; Merlin-Arthur; Arthur-Merlin; CD complexity; CND complexity

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D15: Complexity of computation (including implicit computational complexity)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68Q19: Descriptive complexity and finite models

Related Items

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