[Nouvelles barrières en théorie de la complexité : sur l'indice de complexité de la resolubilité et les tours d'algorithmes]
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.
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.
Accepté le :
Publié le :
@article{CRMATH_2015__353_10_931_0,
author = {Ben-Artzi, Jonathan and Hansen, Anders C. and Nevanlinna, Olavi and Seidel, Markus},
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},
url = {http://www.numdam.org/articles/10.1016/j.crma.2015.08.002/}
}
TY - JOUR AU - Ben-Artzi, Jonathan AU - Hansen, Anders C. AU - Nevanlinna, Olavi AU - Seidel, Markus 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 UR - http://www.numdam.org/articles/10.1016/j.crma.2015.08.002/ DO - 10.1016/j.crma.2015.08.002 LA - en ID - CRMATH_2015__353_10_931_0 ER -
%0 Journal Article %A Ben-Artzi, Jonathan %A Hansen, Anders C. %A Nevanlinna, Olavi %A Seidel, Markus %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 %U http://www.numdam.org/articles/10.1016/j.crma.2015.08.002/ %R 10.1016/j.crma.2015.08.002 %G en %F CRMATH_2015__353_10_931_0
Ben-Artzi, Jonathan; Hansen, Anders C.; Nevanlinna, Olavi; Seidel, Markus. New barriers in complexity theory: On the solvability complexity index and the towers of algorithms. Comptes Rendus. Mathématique, Tome 353 (2015) no. 10, pp. 931-936. doi : 10.1016/j.crma.2015.08.002. http://www.numdam.org/articles/10.1016/j.crma.2015.08.002/
[1] 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] Solving the quintic by iteration, Acta Math., Volume 163 (1989) no. 3–4, pp. 151-180
[3] 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] Families of rational maps and iterative root-finding algorithms, Ann. Math. (2), Volume 125 (1987) no. 3, pp. 467-493
[5] On degrees of unsolvability, Ann. Math. (2), Volume 69 (1959), pp. 644-653
[6] The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.), Volume 4 (1981) no. 1, pp. 1-36
Cité par Sources :
