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[1],[2],[3],[4].
La conjecture doit son nom à Leonard C. Berman et Juris Hartmanis.
Références modifier
- Jörg Rothe, Complexity Theory and Cryptology : An Introduction to Cryptocomplexity, Birkhäuser, , 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, , 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, , 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, , 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).
