Un article de 60 pages censé prouver P ≠ NP a été balancé sur le web il y a dix jours par un dénommé Vinay Deolalikar, chercheur chez HP.

Pour remettre dans le contexte, une preuve correcte répondant enfin à la question "Est-ce que P et NP sont confondus ou pas ?" (c'est-à-dire "Existe-t-il ou non un problème NP qui n'est pas soluble en un temps polynomial ?") sera récompensée par un prix d'un million de dollars, rien que ça.

En guise d'entrée en matière, vous pouvez voir cet article de Wikipedia sur la complexité d'un problème d'optimisation. Vous avez ensuite l'article sur le problème "P/NP".

C'est bon ? Vous êtes chauds ? Alors courage, voici l'article de Vinay Deolalikar :

http://www.scribd.com/doc/35539144/pnp12pt pour une lecture en ligne.
http://www.win.tue.nl/~gwoegi/P-versus- … alikar.pdf pour l'article en PDF.

Et un petit bonus, dans la langue de Shakespeare, sur l'importance d'une telle démonstration.

Si j'ai le courage de lire tout ça moi-même, je répondrai aussi bien que je pourrai aux questions que les deux ou trois potentiellement intéressés de ce forum pourraient avoir. A l'inverse, si je me galère, j'espère que d'autres y auront jeté un oeil