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)
Solving the Rubik's Cube Optimally is NP-complete
- edimd
- Passe sa journée ici. Et dort ici, aussi
- Messages : 851
- Enregistré le : sam. avr. 11, 2015 3:19 pm
- Localisation : Vannes
- Contact :
Re: Solving the Rubik's Cube Optimally is NP-complete
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
- Contact :
Re: Solving the Rubik's Cube Optimally is NP-complete
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)
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)
Odder: Bruno, Oka and I?
Odder: we are all pretty god damn fast when we are not messing around :p and you are... just fucking retarded fast in comps >;.<'
Odder: we are all pretty god damn fast when we are not messing around :p and you are... just fucking retarded fast in comps >;.<'
- Cubeur-manchot
- VIP au club des 1000
- Messages : 2999
- Enregistré le : jeu. sept. 11, 2014 5:16 pm
- Localisation : Bures-sur-Yvette (91)
- Contact :
Re: Solving the Rubik's Cube Optimally is NP-complete
Intéressant, je lirai ça en détails d'ici peu, c'est certain
-
- Passe sa journée ici. Et dort ici, aussi
- Messages : 832
- Enregistré le : mar. janv. 19, 2016 7:06 am
- Contact :
Re: Solving the Rubik's Cube Optimally is NP-complete
J'ai des amis qui le font en genre, 5 secondes !