1988 Reports

# On the Structure of Solutions of Computable Real Functions

The relationship between the structure of a domain and the complexity of computing over that domain is a fundamental question of computer science. This paper studies how the structure of the real numbers constrains the behavior of computable real functions. In particular, we uncover a close correlation between the structure of the zero set of a computable real function, and the complexity of the zeros. We show that computable real functions with hard solutions perforce have many solutions. Furthermore, as the complexity of solutions increases, the number of solutions increases. We prove that computable real functions with nonrecursive, nonarithmetical, or random zeros have solution sets that are, respectively, infinite,“˜ uncountable, or of positive measure. In addition, we show that the computational complexity of the zero set of a computable real function is limited by its topological complexity. These results suggest an emerging paradigm-the inability of machines to name complex strings can serve as the basis of powerful proof techniques in computational complexity theory.

## Subjects

## Files

- CUCS-344-88.pdf application/pdf 505 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-344-88
- Published Here
- December 17, 2011