Francocube

Un article a été posté la semaine dernière sur arXiv, prouvant que résoudre un Rubik's Cube NxNxN de manière optimale est NP-complet.

L'article en question : https://arxiv.org/abs/1706.06708
Cliquez sur PDF en haut à droite pour le télécharger.

Je pourrai faire un résumé et une brève explication cette semaine si ça intéresse ceux qui ne sont pas très versés en maths ou en anglais. (Je précise que je n'ai pas la moindre éducation formelle en maths donc je ne suis pas une référence non plus)

J'ai regardé sur wikipédia pour comprendre ce qu'est un problème N-P complet et... J'ai rien compris

Je vais tenter un truc rapidement :
Un problème P est un problème dont on peut trouver une solution en un temps polynomial (en la taille du problème, pour le cube nxn la taille n par exemple)
Un problème NP est un problème dont on peut vérifier qu'une proposition de solution donnée est effectivement une solution en temps polynomial.

Une question qu'on se pose aujourd'hui c'est de savoir si P = NP, c'est à dire si les problèmes NP sont aussi P ou pas forcément (ça fait partie des problèmes du millénaire, qui peuvent rapporter 1 million de dollars à ceux qui les prouvent (ou qui prouvent le contraire, que certains problèmes NP ne sont pas P))
Un problème NP-complet est un problème NP "difficile", dans le sens où si on arrivait à prouver que ce problème en particulier est P, on aurait P = NP.

C'est pas vraiment des maths, plutôt de l'info théorique.
Globalement on peut retenir que la résolution du Rubik's Cube nxn c'est très compliqué. (D'ailleurs si j'ai bien compris dans la première lecture que j'ai faite en diagonale, c'était plutôt savoir si une position donnée était résoluble en moins de un certain nombre de moves)

Intéressant, je lirai ça en détails d'ici peu, c'est certain

oranjules a écrit : ↑mar. juin 27, 2017 11:53 pmGlobalement on peut retenir que la résolution du Rubik's Cube nxn c'est très compliqué.

J'ai des amis qui le font en genre, 5 secondes !