There Exists a Problem Whose Computational Complexity Is Any Given Function of the Information Complexity
Ming Chu · Journal of Complexity · 1994
We present an information-based complexity problem for which the computational complexity can be any given increasing function of the information complexity, and the information complexity can be any non-decreasing function of ϵ−1, where ϵ is the error parameter.