Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
From MaRDI portal
Publication:424551
DOI10.1016/j.apal.2011.12.030zbMath1259.03059OpenAlexW2033819630MaRDI QIDQ424551
Publication date: 1 June 2012
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2011.12.030
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Numerical linear algebra (65F99) Theory of numerations, effectively presented structures (03D45) Computation over the reals, computable analysis (03D78)
Related Items
Comparing representations for function spaces in computable analysis, Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism, Relative computability and uniform continuity of relations, Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy, Representations of Analytic Functions and Weihrauch Degrees, Decomposing Borel functions using the Shore–Slaman join theorem, Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision, Lawvere-Tierney topologies for computability theorists
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Closed choice and a uniform low basis theorem
- Computability in linear algebra
- On finitely continuous Darboux functions and strong finitely continuous functions
- Computable invariance
- Analytic machines
- Computability on continuous, lower semi-continuous and upper semi-continuous real functions
- On the computability of Walsh functions.
- Recent progress in exact geometric computation
- Topological complexity with continuous operations
- Real hypercomputation and continuity
- The Arithmetical Hierarchy of Real Numbers
- HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
- On the (semi)lattices induced by continuous reducibilities
- Weihrauch degrees, omniscience principles and weak computability
- Effective Choice and Boundedness Principles in Computable Analysis
- Effective Borel measurability and reducibility of functions
- Sample solutions of stochastic ordinary differential equations∗
- Computability theory of generalized functions
- Singular coverings and non‐uniform notions of closed set computability
- Effectivity and effective continuity of multifunctions
- Descriptive set theory and harmonic analysis
- A transfinite hierarchy of reals
- Revising Type-2 Computation and Degrees of Discontinuity
- Computability in Analysis and Physics
- A variant of the Kolmogorov concept of complexity
- Hierarchies of Effective Descriptive Set Theory
- New Computational Paradigms
- New Computational Paradigms
- On Computable Numbers, with an Application to the Entscheidungsproblem
