1993 Reports
There Exists a Problem Whose Computational Complexity is Any Given Function of the Information Complexity
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
- cucs-007-93.pdf application/pdf 218 KB Download File
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