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

DOI10.1016/j.crma.2015.08.002zbMath1343.68078arXiv1508.03280OpenAlexW2196390400MaRDI QIDQ889488

Olavi Nevanlinna, Markus 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)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Computation over the reals, computable analysis (03D78)

Related Items (14)

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

Cites Work

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

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