Home

On the Structure of Solutions of Computable Real Functions

Juris Hartmanis; Lane A. Hemachandra

Title:
On the Structure of Solutions of Computable Real Functions
Author(s):
Hartmanis, Juris
Hemachandra, Lane A.
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-344-88
Publisher:
Department of Computer Science, Columbia University
Publisher Location:
New York
Abstract:
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.
Subject(s):
Computer science
Item views:
84
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use