Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

Écrire une réponse

Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide !
Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci.
Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Options
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Retour

Résumé de la discussion

scarta
22-10-2017 07:58:15

J'ai pas compris. C'est quoi qui n'est pas simple dans "trouver 2 grands nombres premiers"? Et surtout pourquoi la factorisation serait aussi simple ?

Parce que sur mon shell, un ssh-keygen va me générer ça en 50 millisecondes. La factorisation devrait se compter en dizaines d'années sur le même poste...

gwen27
21-10-2017 23:33:04

Bah pas trop, parce que si tu sais les multiplier, tu as su les trouver. Donc ce n'est pas plus dur à résoudre qu'à poser.

Voire même plus facile car si tu trouve une multiplication valable, vu l'énoncé, tu n'as même pas besoin de t'assurer qu'ils sont premiers.

Je propose un truc du genre :
http://www.diophante.fr/component/conte … ipopipette

On peut s'en donner à coeur joie en 30 secondes. La réponse est unique. La trouver est galère au possible.

scarta
21-10-2017 22:39:07

Bon sinon un gros classique. Prends 2 très grands nombres premiers et multiplie les.
Factoriser le résultat est plutôt difficile smile

caduk
19-10-2017 00:22:08

Pour la résolution d'un problème linéaire, il existe d'autres méthodes autre que le simplexe qui nécessitent un temps seulement polynomial. Si on veut réellement des problèmes NP ou pire, il faut un problème linéaire en nombre entiers. Mais dans ce cas, la remarque sur l'unicité ne marche plus...
On peut adapter en considérant une relation d'ordre sur N^n ou n est le nombre de variables, et en sélectionnant la solution optimale la plus petite selon cette relation d'ordre.

Pour aller plus loin, on peut considéré les équations diophantiennes, pour lequel il a été prouvé, en relation avec le dixième problème de Hilbert, que tout ensemble énumérable se ramène à la résolution d'une équation diophantienne. Et comme certain ensembles énumérables ne sont pas calculables, je pense que la notion de "on ne peut pas résoudre rapidement"  s'applique bien ici lol
Pour la question 2, on peut aussi adapter pour s'y ramener.
Par exemple, si on a une équation du type P = 0, où les solutions sont difficilement calculable, on pourrait appliquer la même remarque qu'avant avec la relation d'ordre, le problème étant que l'on ne sait pas si il existe une solution...
On peut se ramener à chercher les solutions pour xP = 0, x n'étant pas une variable de P, en cherchant a maximiser x et avec une relation d'ordre sur les autres variables. Ainsi, soit P a des solutions, et la solution recherchée ne sera pas une solution triviale ou x = 0, soit P n'a pas de solution, et dans ce cas x = 0 et on obtient la solution pour les autres en les prenant qui minimisent la relation d'ordre, mais le problème reste de montrer que P n'a pas de solutions...

scarta
18-10-2017 17:34:03

Prenons un problème d'optimisation, en général de complexité exponentielle, résolu avec le simplexe.
La méthode du simplexe reviennent à trouver le meilleur sommet d'un polytope.
Donc, tu génères un polytope, tu as un problème d'optimisation big_smile
Et pour Q2, tu fais juste attention à ce que ta fonction de coût ne soit pas égale pour 2 sommets donnés

Clydevil
18-10-2017 15:52:03

Hello!

(Pour les impatients la vraie question est à la fin, j'introduis just un peu les choses avant)

Q1: Peut on générer rapidement des énoncés de problèmes qu'on ne puisse pas résoudre rapidement?

Les puristes reconnaîtront une problématique autour de P vs NP mais les non-puristes peuvent voir de quoi il s'agit à travers un exemple:

Je prend N points, je décide aléatoirement la couleur de chacun parmi 3 couleurs possibles, je relie au hasard 2 points de couleur différente ensemble et je recommence cette opération jusqu’à avoir un graphe connexe, passé cette étape je continue l’opération tant que ça me plait. Je prend le graphe obtenu, j'efface les couleurs, et je vous le donne et vous demande de me trouver un coloriage de ce graphe en 3 couleurs (tel que deux nœuds reliés soient de couleur différente)
C'est un exemple de processus ou la génération est plus facile que la résolution.
D’après les conjectures actuelles le consensus est de penser que la réponse à Q1 est donc oui.

Ma question:

Q2:
Peut on générer rapidement des énoncés de problèmes qu'on ne puisse pas résoudre rapidement et pour lesquels on puisse garantir que la solution est unique?

Si quelqu'un a déjà vu des trucs a ce sujet ou a des idées perso ça m’intéresse.

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete