211service.com
Que signifie « P contre NP » pour le reste d'entre nous ?
Depuis une semaine, les programmeurs et informaticiens parlent de la dernière tentative visant à résoudre l'une des questions les plus épineuses de l'informatique : le problème P contre NP.
Vinay Deolalikar, chercheur aux laboratoires HP de Palo Alto, en Californie, a publié sa preuve en ligne et l'a envoyée à plusieurs experts dans le domaine le 6 août. Ses collègues ont immédiatement commencé à disséquer la preuve sur des blogs universitaires et des wikis. Les premières réactions étaient respectueuses mais sceptiques, et le consensus actuel est que l'approche de Deolalikar est fondamentalement erronée.
Une preuve solide gagnerait la gloire et la fortune de Deolalikar. le Institut de mathématiques de l'argile à Cambridge, MA, a nommé P contre NP comme l'un de ses problèmes du millénaire et offre 1 million de dollars à quiconque fournit une preuve vérifiée.
Mais P contre NP est plus qu'un simple puzzle mathématique abstrait. Il cherche à déterminer une fois pour toutes quels types de problèmes peuvent être résolus par les ordinateurs, et quels types ne le peuvent pas. Les problèmes de classe P sont faciles à résoudre pour les ordinateurs ; c'est-à-dire que les solutions à ces problèmes peuvent être calculées dans un laps de temps raisonnable par rapport à la complexité du problème. Pendant ce temps, pour les problèmes NP, une solution peut être très difficile à trouver, nécessitant peut-être des milliards d'années de calcul, mais une fois trouvée, elle est facilement vérifiée. (Imaginez un puzzle : trouver le bon arrangement de pièces est difficile, mais vous pouvez dire quand le puzzle est correctement terminé simplement en le regardant.)
Les problèmes de classe NP incluent de nombreux problèmes de correspondance de motifs et d'optimisation qui présentent un grand intérêt pratique, tels que la détermination de l'agencement optimal des transistors sur une puce de silicium, le développement de modèles de prévision financière précis ou l'analyse du comportement de repliement des protéines dans une cellule.
Le problème P contre NP demande si ces deux classes sont réellement identiques ; c'est-à-dire si chaque problème NP est aussi un problème P. Si P est égal à NP, chaque problème NP contiendrait un raccourci caché, permettant aux ordinateurs de leur trouver rapidement des solutions parfaites. Mais si P n'est pas égal à NP, alors aucun de ces raccourcis n'existe et les pouvoirs de résolution de problèmes des ordinateurs resteront fondamentalement et définitivement limités. L'expérience pratique suggère massivement que P n'est pas égal à NP. Mais jusqu'à ce que quelqu'un fournisse une preuve mathématique solide, la validité de l'hypothèse reste sujette à caution.
Même si la preuve de Deolalikar s'avérait solide, la question demeure : quel impact une telle preuve aurait-elle sur les domaines pertinents de l'informatique ?
Superficiellement, on pourrait penser que la réponse n'est pas beaucoup. Prouver que P n'est pas égal à NP ne ferait que confirmer ce que presque tout le monde suppose déjà vrai à des fins pratiques, explique Scott Aaronson , chercheur en complexité au Laboratoire d'informatique et d'intelligence artificielle du MIT.
Par exemple, notre incapacité à factoriser efficacement d'énormes nombres composites (un problème NP classique) constitue la base de la cryptographie moderne, qui sous-tend tout, de la sécurité nationale aux achats sur Amazon.com. Nous n'avons pas besoin d'une preuve formelle que P n'est pas égal à NP pour s'appuyer sur la conjecture, dit Aaronson. Les programmeurs connaissent le problème et seraient ravis de voir que P n'est pas égal à NP prouvé, mais au quotidien, ils savent que reformuler [un problème NP] en quelque chose de plus facile est beaucoup plus logique que d'essayer de résoudre le problème mathématique. problème du siècle.
Parce que les problèmes de classe NP sont si répandus (même les énigmes de sudoku et les recherches d'horaires de compagnies aériennes sur Bing.com sont difficiles en termes de calcul), des solutions de contournement innovantes sont constamment découvertes. L'optimisation stochastique, par exemple, imite le caractère aléatoire des systèmes physiques (tels que le refroidissement des métaux ou la mutation de l'ADN) afin de produire des solutions suffisamment bonnes au lieu de solutions informatiques difficiles.
Les tentatives pour faire face à l'hypothèse que P n'est pas égal à NP nous aident à développer de nouvelles technologies mentales, dit Richard Lipton , un informaticien à Georgia Tech qui étudie le problème P contre NP. Même si nous écrivons des algorithmes depuis des décennies, nous ne comprenons pas pleinement de quoi ils sont capables, poursuit-il. Donc, même si vous prouviez que P n'est pas égal à NP, ce que tout le monde croit déjà, cela devrait élargir radicalement notre compréhension de ces capacités et rendre possible de nombreuses nouvelles choses avec les ordinateurs, en plus de toutes les solutions de contournement astucieuses que nous avons déjà trouvé.
Donc, si des progrès incrémentiels peuvent toujours générer une innovation utile, pourquoi les titans de la recherche industrielle comme Google, Microsoft et HP (qui ont tous refusé de commenter cet article) ne consacrent-ils pas d'énormes équipes de chercheurs au puzzle P n'égale pas NP ? Prouver un négatif est tout simplement incroyablement difficile, et du point de vue [d'une grande entreprise], cela n'a probablement pas beaucoup d'impact sur le prochain trimestre financier ou même les prochaines années de leur activité, dit Lipton. C'est plus un problème à long terme.
Bien sûr, il y a toujours l'alternative : prouver que P Est-ce que en fait égal à NP. Mais ne retenez pas votre souffle, dit Aaronson. Il y a de bonnes raisons pour lesquelles très peu de gens croient que P est égal à NP, dit-il. Si c'était le cas, nous vivrions dans un univers fondamentalement différent, et nous l'aurions probablement déjà remarqué.