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

It is folklore particularly in numerical and computer sciences that, instead of solving some general problem f:X∋x↦f(x)∈Y, additional structural information about the input x∈X (e.g. any kind of promise that x belongs to a certain subset X′⊆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 for a given singular real n×n-matrix A is possible when knowing rank(A)∈{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×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 logn 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+log2n⌋-fold advice—is sufficient and optimal.Our proofs employ, in addition to topological considerations common in Recursive Analysis, also combinatorial arguments.