Accueil🇫🇷Chercher

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

  1. 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 »).
  2. 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 »).
  3. Stuart Kurtz, Steve Mahaney et Jim Royer, Complexity Retrospective, Springer, , 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, , 410 p. (ISBN 978-1-84816-245-7, lire en ligne), « The Isomorphism Conjecture for NP ».

Voir aussi

Articles connexes

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.