Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra
Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra
复制标题
具有最小离散建议的实际计算：非均匀可计算性的复杂性理论及其在有效线性代数中的应用
DOI：
10.1016/j.apal.2011.12.030
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Ziegler
中科院分区：
文献类型：
--
作者：
M. Ziegler
特别是在数值和计算机科学中，有一种民间传说，即不解决某些一般问题f：X <$X <$f（x）∈Y，而是应该利用关于输入x∈X的额外结构信息（例如，x属于某个子集X′ <$X或不属于某个子集X′ <$X的任何类型的承诺）。在真实的数计算的几个例子中，这样的建议甚至造成了可计算性和不可计算性之间的差异。我们把这两个拓扑和组合的复杂性理论的信息，调查几个实际问题有多少意见是必要的，足以使他们可计算。具体来说，当知道秩（A）∈{0，1，.，n-1}时，对于给定的奇异真实的n× n矩阵A，找到齐次线性方程A⋅x→=0的非平凡解是可能的;我们证明了这是最好的可能。类似地，对角化（即找到特征向量的基）一个给定的真实的对称n× n矩阵A是可能的，当知道不同特征值的数量时：1和n之间的整数（后者对应于非退化情况）。我们再次证明，n倍（即大约logn位）的附加信息确实是必要的，以使这个问题（连续和）可计算的;而对于寻找A的某个单个特征向量，提供A的最小维特征空间的维数的截断二进制对数，即，log 1+ log 2n n倍的建议，是足够的和最佳的。我们的证明采用，除了在递归分析中常见的拓扑考虑，也组合参数。
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 A⋅x→=0 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.
登录
查看更多内容
Gasarch, W.I. 和 Martin, G.A.：递归理论中的有界查询
影响因子：
--
作者：
L. Longpré;V. Kreinovich
通讯作者：
V. Kreinovich
实算术层次结构的可计算性和连续性以及 2 类非确定性的力量
DOI：
--
发表时间：
2005
期刊：
Conference on Computability in Europe
影响因子：
--
作者：
M. Ziegler
通讯作者：
M. Ziegler
多值函数连续点集的描述性集合论复杂性
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
Vassilios Gregoriades
通讯作者：
Vassilios Gregoriades
拓扑中的可计算分离，从 T_0 到 T_3
DOI：
--
发表时间：
2009
期刊：
International Conference on Computability and Complexity in Analysis
影响因子：
--
作者：
K. Weihrauch
通讯作者：
K. Weihrauch
拓扑中的可计算分离，从 T0 到 T2
DOI：
--
发表时间：
2010
期刊：
Journal of universal computer science (Online)
影响因子：
--
作者：
K. Weihrauch
通讯作者：
K. Weihrauch