There exists a problem whose computational complexity is any given function of the information complexity

DOI10.7916/D8P55WMPzbMath0824.68050OpenAlexW2064096247MaRDI QIDQ1342516

Ming Chu

Publication date: 16 February 1995

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1994.1024

zbMATH Keywords

information complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

This page was built for publication: There exists a problem whose computational complexity is any given function of the information complexity