On the Solvability Complexity Index Hierarchy and Towers of Algorithms Article Swipe

MAKE IMPACT

Jonathan Ben-Artzi , Matthew J. Colbrook , Anders C. Hansen , Olavi Nevanlinna , M. Seidel · YOU? · · 2015 · Open Access ·

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 $\mathrm{sp}(A)$ of classes of bounded operators $A = \{a_{ij}\}_{i,j \in \mathbb{N}} \in \mathcal{B}(l^2(\mathbb{N}))$, given the matrix elements $\{a_{ij}\}_{i,j \in \mathbb{N}}$, that are sharp in the sense that they achieve the boundary of what a digital computer can achieve. Similarly, for a Schrodinger operator $H = -\Delta+V$, determine the existence of algorithms that can compute the spectrum $\mathrm{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.

Type

article

Language

en

Landing Page

https://arxiv.org/abs/1508.03280v2

OA Status

green

Cited By

1

Related Works

20

OpenAlex ID

https://openalex.org/W2967637640

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2967637640

Canonical identifier for this work in OpenAlex

Title

On the Solvability Complexity Index Hierarchy and Towers of Algorithms

Work title

Type

article

OpenAlex work type

Language

en

Primary language

Publication year

2015

Year of publication

Publication date

2015-08-13

Full publication date if available

Authors

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

List of authors in order

Landing page

https://arxiv.org/abs/1508.03280v2

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/abs/1508.03280v2

Direct OA link when available

Concepts

Hierarchy, Mathematics, Computational complexity theory, Bounded function, Quintic function, Algorithm, Polynomial hierarchy, Polynomial, Mathematical proof, Matrix (chemical analysis), Discrete mathematics, Geometry, Quantum mechanics, Materials science, Economics, Physics, Composite material, Market economy, Nonlinear system, Mathematical analysis

Top concepts (fields/topics) attached by OpenAlex

Cited by

1

Total citation count in OpenAlex

Citations by year (recent)

2020: 1

Per-year citation counts (last 5 years)

Related works (count)

20

Other works algorithmically related by OpenAlex

Full payload