Solving the Rubik's Cube Optimally is NP-complete

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

Solving the Rubik's Cube Optimally is NP-complete

Message par Nameless »

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)
Image
Bannière atoutcubes.com
Avatar du membre
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

Message par edimd »

J'ai regardé sur wikipédia pour comprendre ce qu'est un problème N-P complet et... J'ai rien compris :(
Avatar du membre
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

Message par oranjules »

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)
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 >;.<'
Avatar du membre
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

Message par Cubeur-manchot »

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
Contact :

Re: Solving the Rubik's Cube Optimally is NP-complete

Message par Nameless »

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 !
Image
Répondre