Difficile mais unique @ Prise2Tete

Clydevil · #1

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.

scarta · #2

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
Et pour Q2, tu fais juste attention à ce que ta fonction de coût ne soit pas égale pour 2 sommets donnés

caduk · #3

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
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 · #4

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

gwen27 · #5

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 · #6

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

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

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

Difficile mai unique

#0 Pub

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

DDifficile mais unique

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

difficile mais uniquz

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

Diifficile mais unique

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

DDifficile mais unique

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

difficile lais unique

Réponse rapide

Sujets similaires

Pied de page des forums