Notes on space complexity of integration of computable real functions in Ko-Friedman model

2014/08/11 by Sergey V. Yakhontov, Yakhontov, Sergey V.
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.1408.2364

Some additions

openalex publication_date 2014/08/11 · arxiv created 2014/11/17 · arxiv updated 2014/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In the present paper it is shown that real function g(x)=∫₀^xf(t)dt is a linear-space computable real function on interval [0,1] if f is a linear-space computable C²[0,1] real function on interval [0,1], and this result does not depend on any open question in the computational complexity theory. The time complexity of computable real functions and integration of computable real functions is considered in the context of Ko-Friedman model which is based on the notion of Cauchy functions computable by Turing machines. In addition, a real computable function f is given such that ∫₀¹f∈ FDSPACE(n²)_C[a,b] but ∫₀¹f∉ FP_C[a,b] if FP≠#P.

Related

• On the Complexity of Real Functions
• Computable real function F such that F is not polynomial time computable on [0,1]
• Computability and Complexity over the Product Topology of Real Numbers
• The complexity of computing in continuous time: space complexity is precision
• Parameterized Uniform Complexity in Numerics: from Smooth to Analytic, from NP-hard to Polytime