Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra (Q424551): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
It is well known that many problems from numerical analysis are not computable in the computable analysis (recursive analysis) setting, since computable functions must be continuous. For example, given a real symmetric \(d\times d\) matrix \(A\), it is generally impossible to compute (due to lack of continuity) any eigenvector of \(A\), although in practice one can often find these eigenvectors. Some authors have criticized computable analysis on the grounds of this apparent mismatch between theory and practice. In this paper, the author argues that this criticism misses the point, since in practice some additional information about the problem at hand is usually known, and with this piece of information, one can actually compute the solution (if it exists). For example, the above problem becomes computable if one knows the number of distinct eigenvalues. Using this idea of providing one extra piece of information (the advice), the author presents a complexity theory which is aimed at finding the ``least'' advice needed so that the transition between non-computability to computability occurs. This complexity theory is introduced both for (single-valued) functions and for multi-valued functions (i.e., relations) and several results which establish lower bounds on this complexity are devised. The author then presents an application of this theory to several common problems from numerical analysis (solving linear equations, symmetric matrix diagonalization, finding some eigenvector, root finding). Overall, this is a paper with very interesting ideas and certainly a worthwhile read for anyone interested in the connections between non-continuity and non-computability in the context of computable analysis. | |||
Property / review text: It is well known that many problems from numerical analysis are not computable in the computable analysis (recursive analysis) setting, since computable functions must be continuous. For example, given a real symmetric \(d\times d\) matrix \(A\), it is generally impossible to compute (due to lack of continuity) any eigenvector of \(A\), although in practice one can often find these eigenvectors. Some authors have criticized computable analysis on the grounds of this apparent mismatch between theory and practice. In this paper, the author argues that this criticism misses the point, since in practice some additional information about the problem at hand is usually known, and with this piece of information, one can actually compute the solution (if it exists). For example, the above problem becomes computable if one knows the number of distinct eigenvalues. Using this idea of providing one extra piece of information (the advice), the author presents a complexity theory which is aimed at finding the ``least'' advice needed so that the transition between non-computability to computability occurs. This complexity theory is introduced both for (single-valued) functions and for multi-valued functions (i.e., relations) and several results which establish lower bounds on this complexity are devised. The author then presents an application of this theory to several common problems from numerical analysis (solving linear equations, symmetric matrix diagonalization, finding some eigenvector, root finding). Overall, this is a paper with very interesting ideas and certainly a worthwhile read for anyone interested in the connections between non-continuity and non-computability in the context of computable analysis. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D78 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q17 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65F99 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6040335 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
recursive analysis | |||
Property / zbMATH Keywords: recursive analysis / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
topological complexity | |||
Property / zbMATH Keywords: topological complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
effective linear algebra | |||
Property / zbMATH Keywords: effective linear algebra / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Daniel Silva Graça / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.apal.2011.12.030 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2033819630 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A transfinite hierarchy of reals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Closed choice and a uniform low basis theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4344150 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3373046 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Weihrauch degrees, omniscience principles and weak computability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective Choice and Boundedness Principles in Computable Analysis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computable invariance / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective Borel measurability and reducibility of functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5150974 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Analytic machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3137311 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sample solutions of stochastic ordinary differential equations<sup>∗</sup> / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New Computational Paradigms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4501143 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5547252 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topological complexity with continuous operations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hierarchies of Effective Descriptive Set Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Descriptive set theory and harmonic analysis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4937850 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5812175 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3220809 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4002474 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3671969 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4337021 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A variant of the Kolmogorov concept of complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recent progress in exact geometric computation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4421975 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On finitely continuous Darboux functions and strong finitely continuous functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the computability of Walsh functions. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5322161 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3639064 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the (semi)lattices induced by continuous reducibilities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computability in Analysis and Physics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Singular coverings and non‐uniform notions of closed set computability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effectivity and effective continuity of multifunctions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4934359 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3993279 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Computable Numbers, with an Application to the Entscheidungsproblem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4485693 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3518432 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computability on continuous, lower semi-continuous and upper semi-continuous real functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Arithmetical Hierarchy of Real Numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computability in linear algebra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New Computational Paradigms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Real hypercomputation and continuity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Revising Type-2 Computation and Degrees of Discontinuity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computability theory of generalized functions / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 07:41, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra |
scientific article |
Statements
Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra (English)
0 references
1 June 2012
0 references
It is well known that many problems from numerical analysis are not computable in the computable analysis (recursive analysis) setting, since computable functions must be continuous. For example, given a real symmetric \(d\times d\) matrix \(A\), it is generally impossible to compute (due to lack of continuity) any eigenvector of \(A\), although in practice one can often find these eigenvectors. Some authors have criticized computable analysis on the grounds of this apparent mismatch between theory and practice. In this paper, the author argues that this criticism misses the point, since in practice some additional information about the problem at hand is usually known, and with this piece of information, one can actually compute the solution (if it exists). For example, the above problem becomes computable if one knows the number of distinct eigenvalues. Using this idea of providing one extra piece of information (the advice), the author presents a complexity theory which is aimed at finding the ``least'' advice needed so that the transition between non-computability to computability occurs. This complexity theory is introduced both for (single-valued) functions and for multi-valued functions (i.e., relations) and several results which establish lower bounds on this complexity are devised. The author then presents an application of this theory to several common problems from numerical analysis (solving linear equations, symmetric matrix diagonalization, finding some eigenvector, root finding). Overall, this is a paper with very interesting ideas and certainly a worthwhile read for anyone interested in the connections between non-continuity and non-computability in the context of computable analysis.
0 references
recursive analysis
0 references
topological complexity
0 references
effective linear algebra
0 references
0 references
0 references