On the Structure of Solutions of Computable Real Functions

Title:

On the Structure of Solutions of Computable Real Functions

Author(s):

Hartmanis, Juris
Hemachandra, Lane A.

Date:

1988

Type:

Technical reports

Department:

Computer Science

Permanent URL:

http://hdl.handle.net/10022/AC:P:12025

Series:

Columbia University Computer Science Technical Reports

Part Number:

CUCS34488

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 paradigmthe 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:

111
 Metadata:

text  xml
 Suggested Citation:

Juris Hartmanis, Lane A. Hemachandra,
1988,
On the Structure of Solutions of Computable Real Functions, Columbia University Academic Commons,
http://hdl.handle.net/10022/AC:P:12025.