Solving the Rubik's Cube Optimally is NP-complete

Si VRAIMENT aucun des autres forums ne vous inspire pour poster votre question ...
5 messages Page 1 sur 1
Nameless
Passe sa journée ici. Et dort ici, aussi
Messages : 832
Enregistré le : mar. janv. 19, 2016 7:06 am


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)
edimd
Passe sa journée ici. Et dort ici, aussi
Messages : 851
Enregistré le : sam. avr. 11, 2015 3:19 pm


J'ai regardé sur wikipédia pour comprendre ce qu'est un problème N-P complet et... J'ai rien compris :(
oranjules
"Le slip de Superman !"
Messages : 2837
Enregistré le : lun. août 24, 2009 1:56 pm


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)
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm


Intéressant, je lirai ça en détails d'ici peu, c'est certain :oui:
Nameless
Passe sa journée ici. Et dort ici, aussi
Messages : 832
Enregistré le : mar. janv. 19, 2016 7:06 am


mar. juin 27, 2017 11:53 pmoranjules a écrit :
Globalement 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 !
5 messages Page 1 sur 1