Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra (Q424551)

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.