Ce sujet a été résolu
2sur10
2 ans
Ah non je suis con, c'est justement de tester chaque position d'arrête qui a un temps polynomial, et trouver la combinaison de couleur qui fonctionne qui doit être le point bloquant
il y a 2 ans-PEMT
Je vois l'idée, et en vrai je vois pas pk ça pourrait pas marcher, vu que j'imagine que chaque étape doit avoir un temps de calcul proportionnel à n² (nombres de connections possibles entre n sommets), et qu'à la fin t'as un nombre relativement limité d'étapes
C'est de trouver les arrêtes à ajouter/retirer qui pose problème ?

C'est de trouver les arrêtes à ajouter/retirer qui pose problème ?
réduire le graphe en DAG est calculatoirement super simple (enfin, en ensemble de DAG plutôt pour conserver les infos )
Le problème c'est effectivement qu'à l'ajout d'arête on tombe sur un problème apparemment sous exponentiel et pas spécialement meilleur que les sous expo déjà connues donc RIP BOZO
Mais c'était amusant
Et sur ce, je go me préparer car contrairement à Oib qui ne jure que par les MPs je traine plutôt avec des gens IRL, peace out girl scouts
Le problème c'est effectivement qu'à l'ajout d'arête on tombe sur un problème apparemment sous exponentiel et pas spécialement meilleur que les sous expo déjà connues donc RIP BOZO
Mais c'était amusant
Et sur ce, je go me préparer car contrairement à Oib qui ne jure que par les MPs je traine plutôt avec des gens IRL, peace out girl scouts
I live inside my own world of make-believe
il y a 2 ans
SucksToBeYou
2 ans
blague à part though j'avais réduit le problème P=NP à l'ajout d'une arête dans un graphe qu'on sait optimalement colorié
c'était fun
c'était fun
il y a 2 ans-PEMT
Ca ne m'étonne pas de l'illustre et incorruptible Johnou_Ingram

il y a 2 ans
SaintePasteque
2 ans
Rav t'es belge aussi?!

Tiens en parlant de belges, tu connais l'expression "à côté de (élément A), (élément B) c'est du pipi de chat" ?
Je sais pas si c'est ma meuf qui est conne ou tous les belges
Je sais pas si c'est ma meuf qui est conne ou tous les belges

il y a 2 ans
Sérieux ils connaissent pas du tout?
Y'a plein d'expressions en commun pourtant

Y'a plein d'expressions en commun pourtant

il y a 2 ans
Nan mais je sais que c'est français, c'est moi qui lui ai dit ahi
C'est elle qui a pas compris
Ayaa celle là par contre elle me choque toujours, ça donne envie de juste répondre oui

C'est elle qui a pas compris

Ayaa celle là par contre elle me choque toujours, ça donne envie de juste répondre oui

il y a 2 ans
Tiens en parlant de belges, tu connais l'expression "à côté de (élément A), (élément B) c'est du pipi de chat" ?
Je sais pas si c'est ma meuf qui est conne ou tous les belges
Je sais pas si c'est ma meuf qui est conne ou tous les belges

Jamais entendu ça de ma vie
il y a 2 ans