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
[+]

 #1 - 18-10-2017 15:52:03

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 851
Lieu: Seahaven island

ifficile mais unique

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.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 18-10-2017 17:34:03

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1533

Difficile mais unnique

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

 #3 - 19-10-2017 00:22:08

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 240

Difficil mais unique

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...

 #4 - 21-10-2017 22:39:07

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1533

diffivile mais unique

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

 #5 - 21-10-2017 23:33:04

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,710E+3

Difficile mais uniuqe

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.

 #6 - 22-10-2017 07:58:15

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1533

Difficil mais unique

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...

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
P2T
Saut de classe? par Mistinguette
28-03-2014 Blabla
22-10-2015 Blabla
31-01-2011 Blabla
P2T
320 bpm par papiauche
05-10-2008 Blabla
16-02-2012 Blabla
17-03-2010 Blabla
26-06-2009 Blabla
P2T
66 par Gadjo
24-12-2010 Blabla
P2T
Star Wars Day par SHTF47
04-05-2012 Blabla

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