2015/08/13 by Jonathan Ben-Artzi, Jonathan Ben‐Artzi, Matthew J. Colbrook +8 · 26 citations
Computer Science · Mathematics · Physics and Astronomy · #34L16 #46N40 (secondary) #47A10 (primary) #81Q10 #Algorithm #Bounded function #Computation #Computational Complexity (cs.CC) #Computational complexity theory #Digital Image Processing Techniques #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Hierarchy #Logic (math.LO) #Mathematical Analysis and Transform Methods #Mathematical Physics (math-ph) #Mathematical analysis #Mathematical proof #Mathematics #Numerical Analysis (math.NA) #Polynomial #Polynomial hierarchy #Quintic function #Spectral Theory (math.SP) #Spectrum (functional analysis) #Topological and Geometric Data Analysis #cs.CC #cs.NA #math-ph #math.LO #math.MP #math.NA #math.SP #msc:34L16 #msc:46N40 #msc:47A10 #msc:81Q10
paper · pdf · doi:10.48550/arxiv.1508.03280
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2015/08/13 · openalex created_date 2019/12/26 · arxiv created 2020/06/15 · arxiv updated 2020/06/16 · openalex updated_date 2026/07/28
This paper establishes some of the fundamental barriers in the theory of computations and finally settles the long-standing computational spectral problem. That is to determine the existence of algorithms that can compute spectra sp(A) of classes of bounded operators A = \aij\i,j ∈ ℕ ∈ B(l2(ℕ)), given the matrix elements \aij\i,j ∈ ℕ, that are sharp in the sense that they achieve the boundary of what a digital computer can achieve. Similarly, for a Schrödinger operator H = -Δ+V, determine the existence of algorithms that can compute the spectrum sp(H) given point samples of the potential function V. In order to solve these problems, we establish the Solvability Complexity Index (SCI) hierarchy and provide a collection of new algorithms that allow for problems that were previously out of reach. The SCI is the smallest number of limits needed in the computation, yielding a classification hierarchy for all types of problems in computational mathematics that determines the boundaries of what computers can achieve in scientific computing. In addition, the SCI hierarchy provides classifications of computational problems that can be used in computer-assisted proofs. The SCI hierarchy captures many key computational issues in the history of mathematics including the insolvability of the quintic, Smale's problem on the existence of iterative generally convergent algorithm for polynomial root finding, the computational spectral problem, inverse problems, optimisation etc.