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

Jonathan Ben-Artzi; Anders C. Hansen; Olavi Nevanlinna; Markus Seidel

doi:10.1016/j.crma.2015.08.002

Functional analysis/Computer science

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

Presented by: the Editorial Board

Jonathan Ben-Artzi ¹; Anders C. Hansen ^2,³; Olavi Nevanlinna ⁴; Markus Seidel ⁵

¹ Department of Mathematics, Imperial College, United Kingdom
² DAMTP, University of Cambridge, United Kingdom
³ Department of Mathematics, University of Oslo, Norway
⁴ Department of Mathematics and Systems Analysis, Aalto University, Finland
⁵ West Saxon University of Applied Sciences, Zwickau, Germany

Comptes Rendus. Mathématique, Volume 353 (2015) no. 10, pp. 931-936.

Abstract
Résumé

We report on new barriers in the theory of computations. These barriers show that the standard theory of computations and complexity theory is insufficient for many core problems in computational theory. Thus we are in need for a new extended complexity theory. The new theory settles the long-standing computational spectral problem and also provides new fundamental algorithms for quantum mechanics.

On met en evidence de nouvelles barrières en théorie du calcul. Ces barrières montrent que la théorie standard du calcul et, en particulier, la théorie de la complexité ne résolvent pas de nombreux problèmes de base de la théorie du calcul. On se trouve face à la nécessité d'une extension de la théorie de la complexité. Cette nouvelle théorie conduit à la résolution d'un problème ancien concernant le calcul spectral. Elle conduit aussi à l'élaboration de nouveaux algorithmes fondamentaux utiles en mécanique quantique.

Received: 2015-06-10
Accepted: 2015-08-19
Published online: 2015-10-01

DOI: 10.1016/j.crma.2015.08.002

Author's affiliations:

Jonathan Ben-Artzi ¹; Anders C. Hansen ^{2, 3}; Olavi Nevanlinna ⁴; Markus Seidel ⁵

¹ Department of Mathematics, Imperial College, United Kingdom
² DAMTP, University of Cambridge, United Kingdom
³ Department of Mathematics, University of Oslo, Norway
⁴ Department of Mathematics and Systems Analysis, Aalto University, Finland
⁵ West Saxon University of Applied Sciences, Zwickau, Germany

@article{CRMATH_2015__353_10_931_0,
     author = {Jonathan Ben-Artzi and Anders C. Hansen and Olavi Nevanlinna and Markus Seidel},
     title = {New barriers in complexity theory: {On} the solvability complexity index and the towers of algorithms},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {931--936},
     publisher = {Elsevier},
     volume = {353},
     number = {10},
     year = {2015},
     doi = {10.1016/j.crma.2015.08.002},
     language = {en},
}

TY  - JOUR
AU  - Jonathan Ben-Artzi
AU  - Anders C. Hansen
AU  - Olavi Nevanlinna
AU  - Markus Seidel
TI  - New barriers in complexity theory: On the solvability complexity index and the towers of algorithms
JO  - Comptes Rendus. Mathématique
PY  - 2015
SP  - 931
EP  - 936
VL  - 353
IS  - 10
PB  - Elsevier
DO  - 10.1016/j.crma.2015.08.002
LA  - en
ID  - CRMATH_2015__353_10_931_0
ER  -

%0 Journal Article
%A Jonathan Ben-Artzi
%A Anders C. Hansen
%A Olavi Nevanlinna
%A Markus Seidel
%T New barriers in complexity theory: On the solvability complexity index and the towers of algorithms
%J Comptes Rendus. Mathématique
%D 2015
%P 931-936
%V 353
%N 10
%I Elsevier
%R 10.1016/j.crma.2015.08.002
%G en
%F CRMATH_2015__353_10_931_0

Jonathan Ben-Artzi; Anders C. Hansen; Olavi Nevanlinna; Markus Seidel. New barriers in complexity theory: On the solvability complexity index and the towers of algorithms. Comptes Rendus. Mathématique, Volume 353 (2015) no. 10, pp. 931-936. doi : 10.1016/j.crma.2015.08.002. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2015.08.002/

References
Cited by

[1] J. Ben-Artzi; A.C. Hansen; O. Nevanlinna; M. Seidel Can everything be computed? – On the solvability complexity index and towers of algorithms, 2015 http://www.damtp.cam.ac.uk/research/afha/anders/SCI.pdf

[2] P. Doyle; C. McMullen Solving the quintic by iteration, Acta Math., Volume 163 (1989) no. 3–4, pp. 151-180

[3] A.C. Hansen On the solvability complexity index, the n-pseudospectrum and approximations of spectra of operators, J. Amer. Math. Soc., Volume 24 (2011) no. 1, pp. 81-124

[4] C. McMullen Families of rational maps and iterative root-finding algorithms, Ann. Math. (2), Volume 125 (1987) no. 3, pp. 467-493

[5] J.R. Shoenfield On degrees of unsolvability, Ann. Math. (2), Volume 69 (1959), pp. 644-653

[6] S. Smale The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.), Volume 4 (1981) no. 1, pp. 1-36

Cited by Sources:

Comments - Policy