Academic Commons

Reports

There Exists a Problem Whose Computational Complexity is Any Given Function of the Information Complexity

Chu, Ming

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.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-007-93
Published Here
January 25, 2012