New barriers in complexity theory: on the solvability complexity index and the towers of algorithms

DOI10.1016/J.CRMA.2015.08.002zbMATH Open1343.68078arXiv1508.03280OpenAlexW2196390400MaRDI QIDQ889488FDOQ889488

Olavi Nevanlinna, M. Seidel, Jonathan Ben-Artzi, Anders C. Hansen

Publication date: 6 November 2015

Published in: Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Abstract: 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 $mathrmsp(A)$ of classes of bounded operators $A={a_{ij}}_{i,jinmathbbN}inmathcalB(l^2(mathbbN))$, given the matrix elements ${a_{ij}}_{i,jinmathbbN}$, that are sharp in the sense that they achieve the boundary of what a digital computer can achieve. Similarly, for a Schr"odinger operator $H=-Delta+V$, determine the existence of algorithms that can compute the spectrum $mathrmsp(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.

Full work available at URL: https://arxiv.org/abs/1508.03280

Recommendations

• On the solvability complexity index, the \(n\)-pseudospectrum and approximations of spectra of operators
• scientific article; zbMATH DE number 4060720
• Complexity theory for operators in analysis
• Complexity issues in computing spectra, pseudospectra and resolvents
• Computational complexity theory and the philosophy of mathematics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computation over the reals, computable analysis (03D78) Spectrum, resolvent (47A10) Selfadjoint operator theory in quantum theory, including spectral analysis (81Q10) General topics in the theory of algorithms (68W01) General topics in the theory of computing (68Q01)

Cites Work

• The fundamental theorem of algebra and complexity theory
• On degrees of unsolvability
• On the Solvability Complexity Index, the 𝑛-pseudospectrum and approximations of spectra of operators
• Families of rational maps and iterative root-finding algorithms
• Solving the quintic by iteration

Cited In (17)

• On the solvability complexity index for unbounded selfadjoint and Schrödinger operators
• On the infinite-dimensional QR algorithm
• On the computation of geometric features of spectra of linear operators on Hilbert spaces
• Computing scattering resonances
• Universal algorithms for computing spectra of periodic operators
• Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation
• On spectral inclusion sets and computing the spectra and pseudospectra of bounded linear operators
• Spectral instabilities: variations on a theme loved by Brian Davies
• A topological view on algebraic computation models
• Spectra of Jacobi operators via connection coefficient matrices
• Spectral approximation of generalized Schrödinger operators via approximation of subwords
• The foundations of spectral computations via the solvability complexity index hierarchy
• On the complexity of the inverse Sturm-Liouville problem
• Computing eigenvalues of the Laplacian on rough domains
• Infinite-dimensional features of matrices and pseudospectra
• Computing the sound of the sea in a seashell
• Moduli of regularity and rates of convergence for Fejér monotone sequences

This page was built for publication: New barriers in complexity theory: on the solvability complexity index and the towers of algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q889488)