Elektrine lite

← Feed

@pyviv@social.sciences.re

2026-03-20 12:40 UTC

En gros, en théorie de la complexité, on range les problèmes en fonction de à quel point on peut les résoudre de façon efficace ou non. Et en gros, on a des problèmes qu'on sait résoudre pas trop mal et d'autres pas du tout Ceux qu'on sait pas résoudre, on a jamais réussi à démonter que c'était vraiment pas possible de le faire de façon efficace, mais on pense que c'est une impossibilité structurelle inhérente au problème lui même, c'est la conjoncture que "P est différent de NP" Mais on a mis tous les problèmes irrésolubles ensemble et on a démontré qu'ils étaient équivalent entre eux (en gros, si on sait en résoudre un, on sait résoudre les autres _ si je sais calculer un certain bidule dans un graphe, je vais réussir à calculer une solution d'une certaine équation)

Replies (1)

  • @pyviv@social.sciences.re 2026-03-20 12:47

    Et tous ces problèmes "équivalents" et qu'on sait pas résoudre mieux, on les appelle des problèmes "NP complet" (c'est très résumé hein, mais c'est l'idée générale)

    Open ##2339768