Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 19-08-2010 00:34:21

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

P ≠ NP (pour les quelques intérssés)

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 lol



Annonces sponsorisées :

Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
  • |
  • Répondre

#0 Pub

 #2 - 19-08-2010 08:08:35

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1434

P ≠ NP (pour les quelques intérssés)

Wow! C'est pas que ça le résultat soit une surprise (en informatique théorique, on devinait déjà que c'était le cas, mais sans démonstration).
Je vais lire ça en espérant ne pas être déçu (ben oui, il y a tout un tas de démonstrations publiées du théorème de Fermat bien avant celle d'Andrew Wiles, qui se sont avérées incorrectes par la suite...)

 #3 - 19-08-2010 12:34:28

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

P ≠ NP (pour les quelqus intéressés)

Pour le problème "P=NP", on est dans le même cas que pour le théorème de Fermat... Jette un oeil :

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

C'est une liste plus ou moins exhaustive smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #4 - 19-08-2010 13:43:25

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1434

P #8800; NP (pour les quelques intéressés)

J'aime beaucoup la démonstration #10 (par l'absurde) ^^

 #5 - 19-08-2010 20:21:17

VanSS
Habitué de Prise2Tete
Enigmes résolues : 47
Messages : 31

P 𕟀 NP (pour les quelques intéressés)

Selon les spécialistes ce ne sera pas pour ce coup ci
http://rjlipton.wordpress.com/2010/08/1 … mment-4885

Bonne nouvelle vous pouvez continuer à chercher pour le milion de dollars et la medaille Fields, ceci dit il est admis qu'il y a quelques très bonnes idées dans ce papier.

 #6 - 19-08-2010 20:45:32

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

p ≠ np (pour les suelques intéressés)

La discussion est très intéressante, et les contributions de Terence Tao excellentes. En même temps, peut-on s'attendre à moins bien de la part d'un mec qui a donné son nom à son premier théorème à 19 ans ? lol


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #7 - 25-09-2010 00:09:33

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3319

P ≠ NP (pour les quelques iintéressés)

Sujet fort interressant mais quelque peut incompréhensible car je ne sais pas à quoi ça sert de faire ça, je ne suis pas un adept de la langue de "secoue la poire" euh non de Shakespeare lol


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete