Un supercalculateur résout « un problème mathématique ouvert depuis 35 ans »

Un supercalculateur résout « un problème mathématique ouvert depuis 35 ans »

« La plus grosse preuve de l’histoire des mathématiques »

71

Un supercalculateur résout « un problème mathématique ouvert depuis 35 ans »

Trois scientifiques ont prouvé que la bicoloration des triplets de Pythagore n'était pas possible pour tous les entiers. Au-delà de la résolution d'un problème mathématique vieux de 35 ans, la méthode utilisée (solveur SAT) est très intéressante et laisse entrevoir de nombreuses possibilités dans tous les domaines scientifiques.

Les mathématiciens sont un peu joueurs et se posent parfois de drôles de questions, généralement bien difficiles à résoudre. Mais avec les ordinateurs modernes et les avancées dans le domaine de l'algorithmique, la solution est à portée pour certaines énigmes. C'est notamment le cas de... la bicoloration des triplets de Pythagore.

Deux couleurs, trois nombres et des milliards de milliards de possibilités

Le CNRS en donne la définition suivante : il s'agit de savoir s'il « est possible de colorier chaque entier positif en bleu ou en rouge de telle manière qu’aucun triplet d’entiers a, b et c qui satisfait la fameuse équation de Pythagore a²+ b²= c² soient tous de la même couleur ? Par exemple, pour le triplet 3, 4 et 5, si 3 et 5 sont coloriés en bleu, alors 4 doit être rouge ».

Si la question parait simple en apparence, on se doute qu'elle se complique de manière exponentielle lorsque le nombre de triplets à prendre en compte augmente. En 2013, les chercheurs Joshua Cooper et Chris Poirel arrivaient à trouver une solution pour « colorier » des nombres entiers jusqu'à 1 344 sans avoir de triplets qui ne comportent que des nombres de la même couleur. Pour autant, cela ne permet pas de répondre à la question pour les nombres supérieurs. Simplement peut-on affirmer que la réponse est oui jusqu'à 1 344, sans que cela ne laisse présager quoi que ce soit de plus. Frustant pour les mathématiciens, mais un défi intéressant pour d'autres.

bicoloration des triplets de Pythagore
Crédits : Villemin Gerard

Dans un article soumis pour publication le 3 mai, et repris récemment par le journal du CNRS, trois scientifiques (Marijn J. H. Heule, Oliver Kullmann et Victor W. Marek) sont enfin parvenus à trouver la solution ce « problème mathématique ouvert depuis 35 ans ». Et leur réponse est sans ambiguïté : non, il n'est pas possible de colorier des entiers de cette manière.

Jusqu'à 7 824 tout va bien, à 7 825 c'est impossible

 Leur étude montre tout de même qu'il est possible de colorier les entiers positifs jusqu'à 7 824 de manière à ce que tous les triplets de Pythagore aient des nombres des deux couleurs. Les scientifiques ajoutent qu'il existe même plusieurs manières d'y arriver. Les cases blanches dans la représentation ci-dessous sont sans contrainte et peuvent donc être indifféremment bleues ou rouges pour que les conditions du problème soient remplies. Néanmoins, cela devient impossible à partir de 7 825. Inutile d'aller plus loin donc.

Au-delà de cette réponse qui n'apporte rien de plus que la satisfaction de l'avoir trouvée (et qui est présenté à la conférence SAT 2016 à Bordeaux), la méthode utilisée par le trio de scientifiques est très intéressante à analyser. Laurent Simon, du Laboratoire bordelais de recherche en informatique (LaBRI), explique en effet que « pour le prouver, les chercheurs n’ont pas eu d’autres choix que d’y aller “en force” en énumérant et en vérifiant toutes les combinaisons possibles ».

 bicoloration des triplets de PythagoreUne solution qui fonctionne pour les 7 824 premiers entiers (les cases blanches sont sans contrainte de couleur)

Un supercalculateur à la rescousse

Et il y en a des combinaisons : 2^7825, soit environ 10^2355 possibilités à analyser, ou encore 1 suivi de 2 355 zéros. Afin de réduire le champ des possibilités, et donc gagner du temps de calcul (qui prendrait de toute façon trop temps), les chercheurs ont mis en œuvre différentes techniques issues de la théorie des nombres. Ils sont ainsi redescendus à 1 000 milliards (1 000 000 000 000) de combinaisons « seulement ». Sans commune mesure avec le nombre total de possibilités à analyser, mais cela reste tout de même important.

À titre de comparaison, il y a 5 x 10^20 coups possibles au jeu de dames (qui est résolu, c'est-à-dire que toutes les parties possibles et imaginables ont été calculées et enregistrées), tandis que le mathématicien Claude Shannon, estime qu'il y aurait environ 10^120 parties « intéressantes » à jouer aux échecs. Au jeu de Go, une partie comporte 1,4 x 10^768 coups possibles et les intelligences artificielles commencent seulement à prendre le dessus sur les humains, là encore sans calculer toutes les possibilités, mais en ayant recours à l'apprentissage profond et par renforcement. Nous avions détaillé tout cela au sein de cette actualité.

Daniel Le Berre, du Centre de recherche en informatique de Lens (Cril), explique que « l’astuce de l’équipe a ensuite été de découper tous ces cas possibles en un million de paquets différents pour pouvoir résoudre le problème plus facilement ». Les opérations ont ensuite été effectués sur le supercalculateur Stampede de l'université du Texas. Celui-ci comprend plus de 522 000 cœurs de traitement, peut effectuer un billiard (10^15) opérations par seconde et revendique la 116e place mondiale des supercalculateurs.

La solution « pèse » la bagatelle de 200 To

« Il aura fallu alors deux jours au supercalculateur [...] pour passer en revue toutes ces possibilités et apporter la preuve tant attendue, générant pour cela 200 téraoctets de données » indique le CNRS dans son journal. Une fois la « preuve » apportée sur un plateau d'argent par le supercalculateur, encore fallait-il la vérifier.

Le résultat est d'une « taille phénoménale, équivalente à tous les textes numérisés détenus par la bibliothèque américaine du Congrès ; c’est la plus grande preuve mathématique jamais produite » et « Il faudrait 10 milliards d’années à un être humain pour la lire »  explique le centre de la recherche scientifique. Bref, c'est là encore un ordinateur qui s'est chargé de cette besogne, mais avec un programme différent.

Les solveurs SAT au cœur de la résolution de ce problème

Le CNRS ajoute que cette petite révolution a été possible grâce aux solveurs SAT, « de nouveaux algorithmes très efficaces pour résoudre ces problèmes [...] Dans le langage informatique, SAT signifie « satisfiabilité ». Il s’agit d’un formalisme logique qui capture toute la difficulté d’un problème combinatoire pour tenter ensuite de le satisfaire ». Emmanuelle Filiot, de l'université libre de Bruxelles, expliquait en 2012, qu'un « solveur SAT est un programme qui décide automatiquement si une formule de logique propositionnelle est satisfaisable ».

Deux exemples parmi d'autres : les jeux de Sudoku (voir ici pour un exemple pratique) ou un démineur, de « très simples problèmes qui peuvent être appréhendés et résolus très facilement par ce formalisme », même si cela peut aller beaucoup plus loin. Daniel Le Berre de l'université d'Artois, explique au CNRS que s'ils étaient pendant un temps réservé à l’informatique théorique, leur utilisation explose et ils permettent désormais « de résoudre des problèmes de plus en plus difficiles ».

Nombre couleurs
Crédits : Berezko/iStock

Traitement rapide des problèmes avec de nombreuses variables et clauses

Dans les exemples d'applications actuelles, il est question de champs assez vastes allant du diagnostic d'erreur sur les circuits électroniques à l'intelligence artificielle. En 2012, Gilles Schaeffer, directeur de recherche au CNRS, ajoutait même que « l’utilisation de solveurs SAT génériques concurrence les algorithmes ad hoc pour certains problèmes d’optimisation combinatoire ».

C'est encore trop obscur pour vous ? En 2012 toujours, le blog d'Ozwald donnait quelques exemples pratiques (même si ces informations ont quatre ans, l'idée générale reste la même) : « Là où ça devient intéressant, c'est qu'on peut faire beaucoup plus que des mini problèmes. Parmi les fichiers cnf mis à dispositions ici on en trouve un qui compte 1 040 variables et 3 668 clauses que Minisat résout (comme "UNSATISFIABLE") en... 0m0.013 s ! Dans la même catégorie on trouve un autre fichier de test contenant 1501 variables et 3575 clauses que Minisat résout (en "SATISFIABLE" avec une solution exemple) en 0m0.008 s ». Un traitement des plus rapides donc, et les choses ont encore dû s'améliorer depuis.

Vous l'aurez compris : de manière générale, les solveurs SAT permettent parfois d'obtenir de bons résultats, surtout lorsqu'il n'existe pas d'autres options que la « force brute  », ce qui est exactement le cas dans la bicoloration des triplets de Pythagore.

Pour ce dernier, c'est le programme Glucose qui a été utilisé, un solveur SAT développé par Gilles Audemard et Laurent Simon. Il a été récompensé à plusieurs reprises lors de compétitions internationales et le code source peut être téléchargé par ici. En 2014, c'est également Glucose qui avait déjà permis de construire la plus longue preuve mathématique de l'époque note le CNRS.

Glucose
Crédits : LaBRI

Microsoft et Intel utilisent déjà les solveurs SAT, d'autres applications en route

Ce dernier ajoute que, « aujourd’hui, Microsoft fait appel à ces algorithmes pour tester ses nouveaux systèmes d’exploitation. Il s’agit alors d’identifier une succession d’instructions parmi des millions susceptibles de causer un bug dans le logiciel ou au contraire de prouver qu’il n’y en aura pas. Même chose pour Intel qui vérifie grâce à ces outils le bon fonctionnement de ses microprocesseurs. Et le nombre d’applications ne cesse de croître en robotique, en bio-informatique ou encore en cryptographie ». L'intelligence artificielle et les solveurs SAT sont aussi étroitement liés, comme on peut facilement s'en douter.

Laurent Simon, coauteur du logiciel Glucose, explique que « ce dernier résultat [NDLR : la bicoloration des triplets de Pythagore] montre qu’il est possible de s’attaquer avec cette méthode à des problèmes mathématiques combinatoires extrêmement difficiles, pour lesquels aucune approche classique à la main n’est encore disponible. Il préfigure probablement la fin d’autres conjectures similaires qui résistent encore aujourd’hui aux mathématiciens ».

Il faut donc s'attendre à ce que les choses évoluent, que ce soit pour les mathématiques, l'informatique et les sciences de manière générale. Dans tous les cas, il reste une question, comme le note de manière ironique Gérad Villemin sur son blog : « Ce type de preuve établit des faits sans les expliquer. Pourquoi 7 824 ? ». On vous laisse méditer sur cette nouvelle question...

Commentaires (71)


lol cette nouvelle change ma vie <img data-src=" />


« Ce type de preuve établit des faits sans les expliquer. Pourquoi 7 824 ? »



Parce que 42. &nbsp;<img data-src=" />



A+


Comme précisé dans l’actu, le plus important ce n’est pas la réponse à la question, mais la manière d’y arriver ;)


Très intéressant, merci!


Merci pour cet article très intéressant <img data-src=" />

Et c’est sur que l’algorithme ne peut pas fournir une explication logique sur le chiffre “7824” il n’est pas la pour ça. Mais les chercheurs vont se pencher dessus, c’est peut-être lié à des problèmes combinatoires à partir de 3 éléments =&gt; 3 chiffres, 2 couleurs, 2 équations (jamais 3 bleus ou 3 rouges / a²+b²=c²).


J’ai lu, mais à mon avis, il me faut le relire :)

Parce que je ne suis pas sûr d’avoir tout compris. <img data-src=" />


Ca n’a rien d’une preuve ni d’une démonstration, vu que ce n’est pas démontré pour TOUTES les combinaisons de nombre possibles. C’est juste une confirmation numérique que ca semble fonctionner jusqu’à un certain rang.



La preuve, c’est lorsqu’on aura démontré que c’est tout le temps vrai ou pas, ou pourquoi sur un certain rang



EDIT : ici on a juste montré qu’une propriété empirique fonctionne sur un intervalle donné, sans trop savoir pourquoi, mais on a poussé les calculs pour savoir jusqu’à quand “ca ne marche plus”


non justement. Une (et même plusieurs) solution existe pour les 7824e premiers entiers, mais c’est impossible à partir du 7825e. Donc pas la peine de continuer&nbsp;<img data-src=" />








Spirit_twin a écrit :



Merci pour cet article très intéressant <img data-src=" />

Et c’est sur que l’algorithme ne peut pas fournir une explication logique sur le chiffre “7824” il n’est pas la pour ça. Mais les chercheurs vont se pencher dessus, c’est peut-être lié à des problèmes combinatoires à partir de 3 éléments =&gt; 3 chiffres, 2 couleurs, 2 équations (jamais 3 bleus ou 3 rouges / a²+b²=c²).





C’est en soi un problème combinatoire, donc bien évidemment que c’y est lié <img data-src=" />&nbsp;



Pour revenir au problème et à la méthode de résolution, je ne connaissais pas Glucose, mais je connais bien le LaBRI, tous ceux qui ont fait des études d’informatiques à Bordeaux I sont passés par là ;) …&nbsp;



Pour ma part je n’aurai pas pensé que ce résultat soit si long à trouver … 7824 c’est pas gigantissime, et une bicoloration si je ne m’abuse ne laisse pas un nombre de combinaison très élevé à chaque palier …

Combien de triplets de pythagores sont présents entre 1 et 7824 ? Au vu du graphique présenté, entre 1000 et 2000 facilement.

Combien de ces triplets verrouillent les solutions précédentes ?

Que l’on commence rouge ou que l’on commence bleu c’est la même chose dans le cadre de la résolution d’un tel problème …&nbsp;

Enfin bref j’imagine que niveau optimisations ils m’ont pas attendu pour réduire la fenêtre de calcul au maximum !



Maintenant messieurs les mathématiciens, à vous d’expliquer 7824 … <img data-src=" />



Il reste à en faire la démonstration <img data-src=" />



Le match déduction vs induction continue <img data-src=" />


Pour montrer qu’une propriété est fausse un contre exemple suffit. La on a un contre contre exemple (trouvé de maniere empirique certe mais ça reste un contre exemple) ça suffit pour dire que la propriété est fausse, pas la peine de chercher plus loin.


Non c’est suffisant pour une démonstration (qui infirme l’énoncé)



“Un nombre puissance 3 ne peut pas être négatif”

Heuuu … “-1”

Il est prouvé que c’est faux.

Pas besoin de chercher toute les combinaisons. C’est ce qu’ils ont fait.

Ils ont prouvé que c’est vrais dans un interval cependant.


Et d’après l’article, ils ont également prouvé que c’est impossible au delà de 7824 (calcul de toutes les combinaisons pour 7825).

Je vais chercher un peu plus pendant mes vacances moi sur ce thème moi, ca va m’occuper ^^


Balèze, on devrait soumettre la question des voyages en hyper-espaces, en lui refilant tout nos connaissance, on sait jamais.<img data-src=" />


Et la conjecture de Riemann, on est ou ? <img data-src=" />


J’attends toujours la résolution du mystère qu’est la femme via ces supercalculateurs <img data-src=" />


C’est un mystère sans solution.<img data-src=" />


<img data-src=" />








SrBelial a écrit :



Maintenant messieurs les mathématiciens, à vous d’expliquer 7824 … <img data-src=" />





Mesdames et messieurs si ça ne vous dérange pas !

&nbsp;



Bon après avoir relus la définition du problème une bonne dizaine de fois, je crois (<img data-src=" />) que j’ai compris pourquoi çà prend du temps : c’est principalement à cause “des cases blanches”. Dès qu’on a une case blanche il faut faire les tests en double… et si on croise une autre blanche rebelotte, ca fini par prendre de la place en mémoire forcément <img data-src=" />



Les vases blanches étant des nombres qui peuvent être bleu ou rouge, ou finir par être bloqué sur une couleur…


J’ai même pas compris l’énoncé du problème&nbsp;<img data-src=" />








Ami-Kuns a écrit :



Balèze, on devrait soumettre la question des voyages en hyper-espaces, en lui refilant tout nos connaissance, on sait jamais.<img data-src=" />







Pour l’instant, la théorie reste à formaliser de manière satisfaisante…



Ca va déjà plus vite avec la touche “Tab” <img data-src=" />


J’ai jamais penser qu’ils le trouverais en quelque jours, mais les calculateurs qui ne sont plus utiliser, peuvent se pencher dessus quelques dizaines d’années.


j’ai absolument rien pigé au problème mais…



200 To de données ! <img data-src=" />

ça en fait du gribouillage High Tech <img data-src=" />



je vais refiler l’article a un pote matheux, il va avoir le kikitoudur <img data-src=" />


on est deux …<img data-src=" />








vinceff a écrit :



on est deux …<img data-src=" />





<img data-src=" />

si on pouvait nous éclairer&nbsp;<img data-src=" />



Au pif, un problème mathématique sans application concrète à priori.


Grossièrement, les mecs ont 2 crayons de couleur et veulent savoir s’ils peuvent colorier des cases sans déborder <img data-src=" />








Vilainkrauko a écrit :



Et la conjecture de Riemann, on est ou ? <img data-src=" />





J’ai une démonstration mais elle est trop longue pour tenir dans l’espace d’un commentaire sur NXI



c’est carrément ça <img data-src=" />








SrBelial a écrit :



Pour ma part je n’aurai pas pensé que ce résultat soit si long à trouver … 7824 c’est pas gigantissime, et une bicoloration si je ne m’abuse ne laisse pas un nombre de combinaison très élevé à chaque palier…

Combien de triplets de pythagores sont présents entre 1 et 7824 ? Au vu du graphique présenté, entre 1000 et 2000 facilement.

Combien de ces triplets verrouillent les solutions précédentes ?

Que l’on commence rouge ou que l’on commence bleu c’est la même chose dans le cadre de la résolution d’un tel problème … 

Enfin bref j’imagine que niveau optimisations ils m’ont pas attendu pour réduire la fenêtre de calcul au maximum !





Pareil, à la lecture de l’énoncé du problème ça ne m’avait pas l’air si calculatoire…







ludo0851 a écrit :



J’ai une démonstration mais elle est trop longue pour tenir dans l’espace d’un commentaire sur NXI





<img data-src=" />









Ami-Kuns a écrit :



J’ai jamais penser qu’ils le trouverais en quelque jours, mais les calculateurs qui ne sont plus utiliser, peuvent se pencher dessus quelques dizaines d’années.







Calculateur plus utilisé, c’est un oxymore…



…ou un engin inutilisable bon pour la casse !



La puissance de calcul, tout le monde en veut et en a besoin, tu peux être sûr que si tu en proposes, aussi bien le secteur public (typiquement, avec la recherche, comme ici) que privé vont te l’acheter et y mettre le prix.



En gros, t’as des dominos bizarres (ils ont trois « côtés ») et un peu spéciaux (les numéros sur les trois côtés respectent une relation mathématique : a²+b²=c²) et tu veux savoir s’il est possible de colorer d’une seule couleur chaque numéro sur l’ensemble des dominos avec seulement un crayon bleu et un crayon rouge (par exemple tous les 4 en bleu, tous les 5 en rouge, etc.) , tout ça sans qu’il y ait un domino qui soit entièrement coloré de la même couleur.


En relisant l’article de wikipédia, je me suis fait la réflexion que ça correspondrait à faire du surf sur une « vague » de l’espace-temps. Du coup je me suis posé la question suivante : est-ce qu’il serait possible de « surfer » sur une onde gravitationnelle ?

Vu que tu as fait pas mal de recherches sur ce genre de sujet pour tes nouvelles, tu peux peut-être me répondre ? <img data-src=" />


Je me réponds à moi-même puisque la réponse est toute bête : oui, puisque la gravitation est une déformation de l’espace-temps. Par contre, elle ne se déplace qu’à la vitesse de la lumière, donc ça ne devrait pas permettre d’aller plus vite…








Mihashi a écrit :



En relisant l’article de wikipédia, je me suis fait la réflexion que ça correspondrait à faire du surf sur une « vague » de l’espace-temps. Du coup je me suis posé la question suivante : est-ce qu’il serait possible de « surfer » sur une onde gravitationnelle ?

Vu que tu as fait pas mal de recherches sur ce genre de sujet pour tes nouvelles, tu peux peut-être me répondre ? <img data-src=" />







J’ai pris comme hypothèse celle selon laquelle la propulsion Alcubierre fonctionne à base de focalisation d’ondes gravitationnelles pour produire la vague en question, l’énergie cinétique d’un navire spatial étant focalisée devant l’engin pour produire la bulle Alcubierre, ce qui nécessite une vitesse de conversion relative d’une certaine valeur (j’ai fixé au pif à 50 km/s pour ne pas décrire des phases d’accélération durant un mois ou deux) et des systèmes permettant de capter, amplifier, moduler et restituer les ondes gravitationnelles. Vitesse maxi théorique : 15000 fois la vitesse de la lumière (là encore, c’est au pif pour les besoins de mes récits)



Après, si quelqu’un a l’idée de développer la technologie disponible, il a un grand avenir dans l’ingénierie astronautique devant lui… <img data-src=" /><img data-src=" /><img data-src=" /><img data-src=" /><img data-src=" />





pour le prouver, les chercheurs n’ont pas eu d’autres choix que d’y aller “en force” en énumérant et en vérifiant toutes les combinaisons possibles





News@11



Des chercheurs ont résolu un problème de dénombrement en testant toutes les combinaisons possibles.



/News@11



<img data-src=" />


Y a de grandes chances que ce problème soit indécidable.








boogieplayer a écrit :



<img data-src=" />

si on pouvait nous éclairer <img data-src=" />









vinceff a écrit :



on est deux …<img data-src=" />







C’est pourtant pas compliqué <img data-src=" />



Le but du jeu est de voir si pour l’opération a²+b²=c² on (a, b et c étant des entiers positifs) on peut toujours n’avoir que 2 des éléments d’une couleur et donc le dernier d’une autre (ici rouge et bleu)



Donc dans les cas listés dans l’image de la news:

a = 3, b = 4 donc c=5 : on décide arbitrairement d’avoir a en bleu , b et c en rouge

Ensuite pour 5, 12 et 13, on a déjà 5 en rouge et ils ont décidés de mettre 12 en rouge et donc il faut mettre 13 en bleu (sinon trois entiers en rouge, ce que l’on veut pas).



Il a donc fallu tester toutes les permutations possibles (tous les entiers et toutes les couleurs “arbitraires”) en recalculant les différences engendrées plus loin (entier fixé sur une couleur, qui a changé dans une itération précédente par exemple)



Trop de variables aléatoires changeants d’états en permanence j’en ai bien peur en effet&nbsp; <img data-src=" />








boogieplayer a écrit :



J’ai même pas compris l’énoncé du problème <img data-src=" />









Je pense que la problématique es trop abstraite.

Je n’ai pas tout pigé non plus mais je pense que ce n’es pas mon genre de délire ^^



Ils ont eu du bol que ce soit faux, si la conjecture avait été vraie le truc tournerait encore, et pour rien d’ailleurs… Je me demande s’ils avaient une intuition que ce serait faux aux alentours de 7800&nbsp; ou s’ils avaient prévu de faire tourner le truc pendant les vacances pour voir en espérant qu’ils en tireraient de quoi faire un article.








Mihashi a écrit :



En gros, t’as des dominos bizarres (ils ont trois « côtés ») et un peu spéciaux (les numéros sur les trois côtés respectent une relation mathématique : a²+b²=c²) et tu veux savoir s’il est possible de colorer d’une seule couleur chaque numéro sur l’ensemble des dominos avec seulement un crayon bleu et un crayon rouge (par exemple tous les 4 en bleu, tous les 5 en rouge, etc.) , tout ça sans qu’il y ait un domino qui soit entièrement coloré de la même couleur.





Merci, ça m’éclaire. J’avoue humblement que je n’arrive pas à mentaliser ce type de problème très abstrait&nbsp;<img data-src=" />









CryoGen a écrit :



C’est pourtant pas compliqué <img data-src=" />



Le but du jeu est de voir si pour l’opération a²+b²=c² on (a, b et c étant des entiers positifs) on peut toujours n’avoir que 2 des éléments d’une couleur et donc le dernier d’une autre (ici rouge et bleu)



Donc dans les cas listés dans l’image de la news:

a = 3, b = 4 donc c=5 : on décide arbitrairement d’avoir a en bleu , b et c en rouge

Ensuite pour 5, 12 et 13, on a déjà 5 en rouge et ils ont décidés de mettre 12 en rouge et donc il faut mettre 13 en bleu (sinon trois entiers en rouge, ce que l’on veut pas).



Il a donc fallu tester toutes les permutations possibles (tous les entiers et toutes les couleurs “arbitraires”) en recalculant les différences engendrées plus loin (entier fixé sur une couleur, qui a changé dans une itération précédente par exemple)





Rien compris, je préfère celle de&nbsp;Mihashi Elle me rappelle Donjon & Dragon&nbsp;<img data-src=" />









x689thanatos a écrit :



Je pense que la problématique es trop abstraite.

Je n’ai pas tout pigé non plus mais je pense que ce n’es pas mon genre de délire ^^





Moi non plus&nbsp;<img data-src=" />



Les mathématiciens cachent leur bornes sous des flots de formules








Mihashi a écrit :



En relisant l’article de wikipédia, je me suis fait la réflexion que ça correspondrait à faire du surf sur une « vague » de l’espace-temps. Du coup je me suis posé la question suivante : est-ce qu’il serait possible de « surfer » sur une onde gravitationnelle ?

Vu que tu as fait pas mal de recherches sur ce genre de sujet pour tes nouvelles, tu peux peut-être me répondre ? <img data-src=" />



En théorie, oui c’est possible. C’est d’ailleurs une des “possibilités” offertes pour dépasser la vitesse de la lumière. Le seul pb, c’est que ca implique un échauffement qui met la coque extérieure à une température qque part entre 110 et 12 fois celle du Soleil <img data-src=" />









numerid a écrit :



Mesdames et messieurs si ça ne vous dérange pas !

&nbsp;





Oups, je demande pardon !! Je suis confus.

(et tellement confus que je ne me chercherai même pas d’excuse du style “oui mais sur NXI l’auditoire est essentiellement masculin” ou “oui mais les mathématiciens sont rarement des mathématiciennes”, parce que ça serait déplacé et ça serait du troll <img data-src=" />)



Excuses acceptées ?&nbsp;<img data-src=" />









Nerkazoid a écrit :



J’attends toujours la résolution du mystère qu’est la femme via ces supercalculateurs <img data-src=" />





C’est un mystère qui n’en est pas un. En fait la femme n’est qu’un homme, mais en mieux.









numerid a écrit :



Mesdames et messieurs si ça ne vous dérange pas !



Sur Internet, toutes les femmes sont des hommes <img data-src=" />









Nerkazoid a écrit :



J’attends toujours la résolution du mystère qu’est la femme via ces supercalculateurs <img data-src=" />



Pourtant c’est pas compliqué <img data-src=" />



Sinon tu as la version livre <img data-src=" />









Northernlights a écrit :



Les mathématiciens cachent leur bornes sous des flots de formules



Jolie !



Et bah c’est plus clair comme ça en tout cas =)



Le premier exemple était déjà trop nébuleux pour moi :p








ludo0851 a écrit :



J’ai une démonstration mais elle est trop longue pour tenir dans l’espace d’un commentaire sur NXI





Dans ce cas … garde la pour toi : les experts cryptage (Voir plus) risquent de passer des nuits blanches a cause de toi !&nbsp; <img data-src=" />



Au contraire, les blanches tendent à simplifier le problème. Un certain nombre d’entre elles ne font pas partie de triplets pythagoriciens (il me semble que c’est le cas de 1 et 2), pour d’autres, elles font partie d’un triplet dont les deux autres membres sont de couleur différente. Cela tend à te simplifier ton problème.



Pour l’explosion combinatoire, c’est expliqué dans l’article : 2^7385 (chaque case peut être soit bleue, soit rouge). Après, un premier moyen simple, c’est de réduire ça aux seuls triplets pythagoriciens (tous les nombres entiers ne font pas partie d’un triplet) : ça doit déjà enlever quelques ordres de grandeur. Je suppose qu’ils ont fait en plus de ça d’autres simplifications moins triviales, et ensuite « use the (brute) force ».


Car 7+8+2+4=21=422&nbsp;<img data-src=" />



CQFD JQCT.


C’est efficace avec des problèmes de complexité NP ces solveurs SAT ?


Oui, cf ici pour plus de détails&nbsp;(cours de&nbsp;Gilles Schaeffer)&nbsp;<img data-src=" />


Merci beaucoup pour cet article.

&nbsp;Très franchement, je ne suis pas sur d’avoir tout compris. Mais, j’apprécie infiniment que les journalistes se décarcassent pour solliciter mon neurone sur un sujet qui n’avait à priori aucune &nbsp;chance de m’intéresser.

&nbsp;Merci à tous ceux qui collaborent à ce site et qui m’ont donné envie de rejoindre les abonnés.&nbsp;


Euh non toutes les “cases” étant testés (pas forcement une valeur “c”, mais obligatoirement une valeur possible de a ou b), tu dois tester si çà marche en rouge, bleu (ce qui implique une couleur qui peut varier pour c du coup) et ainsi de suite.


Merci ! <img data-src=" />


&nbsp; Çaexiste mieux que la perfection déjà incarnée que nous sommes <img data-src=" />


Ah bah voilà, il ne me reste plus qu’à le commander et potasser tout ça <img data-src=" /> Merci <img data-src=" />








gathor a écrit :



Comme précisé dans l’actu, le plus important ce n’est pas la réponse à la question, mais la manière d’y arriver ;)





Tu indiques que le Calculateur à mis 2 jours pour générer 200To de données brutes.

Combien de temps pour les digérer avec l’algo SAT et cracher le nombre ?



Sinon, la réponse universelle est déjà connue… 42 (comme Adriana ^^ )



[]—&gt;



Oh joli !!!! <img data-src=" />


Le compte est bon Michel ! On va maintenant passer aux lettre. Consonne ou voyelle ?


Un domino à trois côtés est un Triomino.




Les opérations&nbsp;ont ensuite été effectués sur&nbsp;le&nbsp;supercalculateur Stampede de l’université du Texas.





On n’a pas de calculateurs suffisants en France pour ce genre d’applications ?


La liste d’attente pour traiter les problemes qui leur sont soumis peut etre longue. Un supercalculateur qui ne travaille pas est une perte sèche.



C’est comme les grues mobiles en france. Pour l’accident de brétigny, c’est une belge qui est venu. On en a en france, mais aucune n’était disponible immédiatement (/sous 7 jours).


Fermer