Dans le même genre on peut prouver aussi que P!=NP, c'est plus simple.
Enfin plus simple, c'est vite dis, car on a juste à trouver un contre exemple que P est différent de NP alors que prouver l'égalité revient à prouver que tout algo P est NP et tout algo NP est P ce qui est achement plus dur.
Au fait, les profs nous ont rabachés qu'il existe un concours (j'ai pas les coordonnées) comme quoi le premier qui montre que P=NP ou P!=NP gagne 1M$ (pas Microsoft, Million de dollars ce qui est plus sympa).
Une piste pour les néophites : il suffit de prouver qu'un algo supra-polynomial peut se raporter à un algo polynomial en un temps polynomial.
[^] # Re: Que ne savons-nous pas ?
Posté par Émilien Kia . En réponse au journal Que ne savons-nous pas ?. Évalué à 1.
Enfin plus simple, c'est vite dis, car on a juste à trouver un contre exemple que P est différent de NP alors que prouver l'égalité revient à prouver que tout algo P est NP et tout algo NP est P ce qui est achement plus dur.
Au fait, les profs nous ont rabachés qu'il existe un concours (j'ai pas les coordonnées) comme quoi le premier qui montre que P=NP ou P!=NP gagne 1M$ (pas Microsoft, Million de dollars ce qui est plus sympa).
Une piste pour les néophites : il suffit de prouver qu'un algo supra-polynomial peut se raporter à un algo polynomial en un temps polynomial.
A vos brouillons :-)
Un jour libre ?