2026-07-20T07:28:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2277 2024-03-06T10:28:38Z ddc:004 open_access

Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability Ziegler, Martin Nonuniform computability recursive analysis topological complexity linear algebra It is folklore particularly in numerical and computer sciences that, instead of solving some general problem $f:A\to B$, additional structural information about the input $x\in A$ (that is any kind of promise that $x$ belongs to a certain subset $A'\subseteq A$) should be taken advantage of. Some examples from real number computation show that such discrete advice can even make the difference between computability and uncomputability. We turn this into a both topological and combinatorial complexity theory of information, investigating for several practical problem show much advice is necessary and sufficient to render them computable. Specifically, finding a nontrivial solution to a homogeneous linear equation $A\cdot\vec x=0$ for a given singular real $n\times n$-matrix $A$ is possible when knowing $\rank(A)\in\{0,1,\ldots,n-1\}$; and we show this to be best possible. Similarly, diagonalizing (i.e. finding a basis of eigenvectors of) a given real symmetric $n\times 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 finding \emph{some single} eigenvector of $A$ requires and suffices with $\Theta(\log n)$--fold advice. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Ziegler 2009 Is Part Of OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.CCA.2009.2277 urn:nbn:de:0030-drops-22770 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2277 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode