Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra

Abstract

It is folklore particularly in numerical and computer sciences that, instead of solving some general problem f : X (sic) x bar right arrow f (x) is an element of Y, additional structural information about the input x is an element of X (e.g. any kind of promise that x belongs to a certain subset X' subset of X, or does not) should be taken advantage of. In several examples from real number computation, such advice even makes the difference between computability and uncomputability. We turn this into a both topological and combinatorial complexity theory of information, investigating for several practical problems how much advice is necessary and sufficient to render them computable.

Specifically, finding a nontrivial solution to a homogeneous linear equation A.(x) over bar for a given singular real n x n-matrix A is possible when knowing rank(A) is an element of {0, 1, ..., n - 1); and we show this to be best possible. Similarly, diagonalizing (i.e. finding a basis of eigenvectors to) a given real symmetric n x n-matrix A is possible when knowing the number of distinct eigenvalues: an integer between 1 and n (the latter corresponding to the nondegenerate case). And again we show that n-fold (i.e. roughly log n bits of) additional information is indeed necessary in order to render this problem (continuous and) computable; whereas for finding some single eigenvector of A, providing the truncated binary logarithm of the dimension of the least-dimensional eigenspace of A-i.e. [1 + log(2) n]-fold advice-is sufficient and optimal.

Our proofs employ, in addition to topological considerations common in Recursive Analysis, also combinatorial arguments. (C) 2012 Elsevier B.V. All rights reserved.