scientific article; zbMATH DE number 1303206
Computability and complexity in analysis (called CCA) is an important research area which applies the well-developed techniques from discrete computability and complexity theory to study the continuous problems from classical mathematics and other areas. This paper is a very good survey about the main topics of CCA. The first part of the paper discusses the computability in analysis. After introducing the computation model, several important results about the computable reals and real functions are discussed, including the roots of computable real functions, the solutions of ordinary differential equations and the computable linear operators. The second part covers the complexity theory in analysis. A quite reasonable complexity measure for real numbers and real functions is introduced. After recalling the basic notions of discrete complexity theory, a lot of numerical problems are classified according to their complexity in terms of discrete complexity classes. These problems include the maximization problem, the root-finding problem, the integration problem, ordinary differential equations and integral equations. At last, several approaches to study the computational complexity of continuous problems are briefly discussed and compared. For the entire collection see [Zbl 0905.03002].
- Comparing representations for function spaces in computable analysis
- Selected papers of the 3rd international conference on computability and complexity in analysis, CCA 2006, Gainesville, FL, USA, November 1--5, 2006
- On the complexity of computing the Hausdorff distance
- Differentiability of polynomial time computable functions
- scientific article; zbMATH DE number 4134023 (Why is no real title available?)
- In Memoriam: Ker-I Ko (1950–2018)
- Nondeterministic polynomial-time computations and models of arithmetic
- scientific article; zbMATH DE number 3932433 (Why is no real title available?)
- Computable Carathéodory theory
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
- On the computational complexity of the Dirichlet problem for Poisson's equation
- scientific article; zbMATH DE number 782052 (Why is no real title available?)
- Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
- Handbook of computability and complexity in analysis
- Weihrauch Complexity in Computable Analysis
- A tutorial on computable analysis
- Non-computable Julia sets
- The computational complexity of distance functions of two-dimensional domains
- Representations of analytic functions and Weihrauch degrees
- Polynomial time computation in the context of recursive analysis
- Proceedings of the 6th workshop on computability and complexity in analysis (CCA 2004), Lutherstadt Wittenberg, Germany, August 16--20, 2004
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249729)