Conjecture de Berman-Hartmanis

En théorie de la complexité, la conjecture de Berman-Hartmanis est une conjecture non résolue qui prétend que tous les langages NP-complets se ressemblent. Plus précisément, la conjecture prétend qu'il existe un isomorphisme calculable en temps polynomial entre tous langages NP-complets^,^,^,.

La conjecture doit son nom à Leonard C. Berman et Juris Hartmanis.

Références

↑ Jörg Rothe, Complexity Theory and Cryptology : An Introduction to Cryptocomplexity, Birkhäuser, 2005, 478 p. (ISBN 978-3-540-22147-0, lire en ligne), chap. =3.6.2 (« The Berman–Hartmanis Isomorphism Conjecture and One-Way Functions »).
↑ Uwe Schöning et Randall J. Pruim, Gems of Theoretical Computer Science, Springer, 1998, 320 p. (ISBN 978-3-540-64425-5), chap. 15 (« The Berman–Hartmanis Conjecture and Sparse Sets »).
↑ Stuart Kurtz, Steve Mahaney et Jim Royer, Complexity Retrospective, Springer, 1990, 108–146 p. (lire en ligne), « The structure of complete degrees »
↑ Manindra Agrawal, S. Barry Cooper (dir.) et Andrea Sorbi (dir.), Computability in Context : Computation and Logic in the Real World, World Scientific, 2011, 410 p. (ISBN 978-1-84816-245-7, lire en ligne), « The Isomorphism Conjecture for NP ».

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Berman–Hartmanis conjecture » (voir la liste des auteurs).

Voir aussi

Articles connexes

Théorème de Mahaney

Liens externes

http://ieeexplore.ieee.org/document/5231233/

Portail de l'informatique théorique

[1] Jörg Rothe, Complexity Theory and Cryptology : An Introduction to Cryptocomplexity, Birkhäuser, 2005, 478 p. (ISBN 978-3-540-22147-0, lire en ligne), chap. =3.6.2 (« The Berman–Hartmanis Isomorphism Conjecture and One-Way Functions »).

[2] Uwe Schöning et Randall J. Pruim, Gems of Theoretical Computer Science, Springer, 1998, 320 p. (ISBN 978-3-540-64425-5), chap. 15 (« The Berman–Hartmanis Conjecture and Sparse Sets »).

[3] Stuart Kurtz, Steve Mahaney et Jim Royer, Complexity Retrospective, Springer, 1990, 108–146 p. (lire en ligne), « The structure of complete degrees »

[4] Manindra Agrawal, S. Barry Cooper (dir.) et Andrea Sorbi (dir.), Computability in Context : Computation and Logic in the Real World, World Scientific, 2011, 410 p. (ISBN 978-1-84816-245-7, lire en ligne), « The Isomorphism Conjecture for NP ».