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
Voir aussi Articles connexes Théorème de Mahaney
Liens externes http://ieeexplore.ieee.org/document/5231233/
Catégorie:Théorie de la complexité des algorithmes