20

[Arsonist]

Il faut qu'il soit intègre, sinon on peut très bien avoir
N=(1 1)
(0 1)
P=(0 0)
(1 0)

Quel abruti je suis.

[Castitatis]

pour moi l'algèbre ça a toujours été la philo des maths...en même temps j'suis pas meilleur en analyse...

[deadalnix]

C'est quoi le phénomène P != NP?

http://fr.wikipedia.org/wiki/Th%C3%A9or ... lgorithmes" onclick="window.open(this.href);return false;

En gros la question est de savoir si on sera capable de résoudre un jour tout problème logique avec un ordinateur ou pas. En effet, les problème polynomiaux peuvent être résolu avec un ordinateur, ou bien, le seront dans le futur avec l'augmentation de la puissance de ceux-ci.

La question est encore ouverte.

[TMOY]

Oui, enfin ça reste quand même théorique. Parce que d'une part la puissance des ordinateurs ne va pas croître indéfiniment, et d'autre part savoir que tel problème a une solution polynômiale, si le polynôme est de degré un milliard ça te fait une belle jambe pour le résoudre...

[pierrotlenageur]

Et comme je suis un Francocubeur modèle, je recolle au sujet :

Ce matin sur BFM tv (je crois qu'il doit encore être à l'antenne):
reportage sur le nombre de dieu!! le reportage dure environ 2 minutes, et histoire que ce soit encore plus amusant, les images sont celles des derniers championnats de France!
On voit Loic s'afferrer au 5*5*5 d'entrée, et après un ensemble de mains, plus ou moins reconnaissable!
J'en ai recraché mon petit dej

[rafoo]

je dirais même, dans tout anneau unitaire,

(p = np <=> (p = 0 \/ n = 1)) <=> l'anneau est intègre

la puissance des ordinateurs ne va pas croître indéfiniment

Rien n'est moins sûr, les temps des speed cubeurs vont-ils descendre indéfiniment ?

si le polynôme est de degré un milliard ça te fait une belle jambe pour le résoudre

Là je suis d'accord avec toi ; je pense que c'est LA limite de la théorie de la complexité : comme je le disais dans mon post précédent, dans cette théorie on en a rien à faire des constantes (le degré du polynôme mais aussi la constante multiplicative) ; dans cette théorie, le temps et l'espace nécessaire à la résolution optimale et l'enregistrement de la solution de tous les 7×7×7 pourra être négligé si bien que la résolution optimale de n cubes 7×7×7 est considérée linéaire alors qu'on est pas prêt d'avoir un algo qui résout vraiment le 7×7×7 de manière optimale (avec la puissance de tous les ordinateurs du monde en un temps inférieur à l'age de l'Univers).

De plus il arrive qu'on sache qu'un problème est polynomial sans même avoir un algo pour le résoudre ; il a été démontré que tester si un graphe peut être dessiné (sans croisement d'arcs) sur un tore (je dis ça de mémoire, je me trompe peut-être) est un problème linéaire : comme pour le cas du plan, il existe une liste finie des cas pathologiques et il suffit de tester qu'aucun élément de cette liste n'apparait dans le graphe ; la différence avec le plan c'est qu'on ne connait pas cette liste et elle n'intéresse pas grand monde parce qu'il est peu probable qu'elle tienne en mémoire sur un ordinateur.

Remarque : j'ai pas vérifié mes sources pour le paragraphe précédent mais même si je me suis trompé d'exemple, l'idée est là.

[frsechet]

C'est quoi le phénomène P != NP?

Eh mais c'est pas moi qui ai écrit ça! (d'autant plus que je connais le problème déjà, et que l'institut Clay m'a déjà contacté pour venir couvrir en reportage la remise d'un de ses "prix Millenium"... bref.)

[Tatsuya]

On a usurpé ton identité alors ?

[Nencaran]

Et comme je suis un Francocubeur modèle, je recolle au sujet :

Ce matin sur BFM tv (je crois qu'il doit encore être à l'antenne):
reportage sur le nombre de dieu!! le reportage dure environ 2 minutes, et histoire que ce soit encore plus amusant, les images sont celles des derniers championnats de France!
On voit Loic s'afferrer au 5*5*5 d'entrée, et après un ensemble de mains, plus ou moins reconnaissable!
J'en ai recraché mon petit dej

Visible là : http://www.bfmtv.com/video-infos-actual ... ue-328758/

[ofapel]

Apparemment, il y a eu un reportage sur direct8. Si quelqu'un a un lien...

[Cuble]

OMG , au debut de la video on voit 3 cubeur ... dont un avec mon cube , que j'avais prété (si je me rapel bien) , facilement reconnaissable , les stickers etait pouris en particulier ceux de la face orange a moitié blanc ^^

[Tatsuya]

il y a aussi http://www.newscientist.com/article/dn1 ... olved.html" onclick="window.open(this.href);return false;

J'avoue être un peu étonné par ça.

First they divided the set of all possible starting configurations into 2.2 billion sets, each containing 19.5 billion configurations, according to how these configurations respond to a group of 10 possible moves.
This grouping allowed the team to reduce the number of sets to just 56 million, by exploiting various symmetries of a cube.

Les symétries permettent de diviser par 40 le nombre de cas à étudier ? ça me parait beaucoup.
Ou alors on ne parle pas seulement des vraies symétries, mais aussi du fait que si on fait le mouvement "x" ( = {R} ), on n'obtient pas un nouveau cas ?

[Arsonist]

Si on considère les 6 orientations, les symétries par rapport à un axe passant par la diagonale, les symétries par un axe passant par deux arêtes... On doit y arriver, non?

[rafoo]

Il y a
24 manière d'orienter le cube (6 choix pour la couleur de F, 4 pour celle de U)
× 2 si on rajoute un miroir (2 choix pour R)
(et en option × 2 en faisant du reverse scrambling).

Le mot "symétrie" dans ce contexte peut prêter à confusion en effet, je pense que la meilleure manière de le dire c'est qu'on a 48 automorphismes qui conservent la métrique (d'ailleurs il serait intéressant de voir s'il y en a d'autres).

Et encore une fois, les termes "group" et "grouping" sont pas super bien choisis.

[Tatsuya]

J'ai pas trop compris tes comptages, je pense qu'on en parlera plutôt à la prochaine RIC.