Discussion :

[Pecose]

Bonjour tout le monde!

Je fais des recherche sur les problème de la classe NP pour mon propre plaisir, et je voudrais savoir si il existe une façon d'exprimer une factorisation d'entier sous la forme d'une instance SAT.

J'ai cherché un peu partout sur google mais je ne trouve pas de réponse et je ne suis pas très fort en anglais :/

Donc voila si quelqu'un connais une méthode j'aimerai bien la connaitre merci. 👍

[dourouc05]

Juste pour le côté NP : a priori, le problème est dans NP, mais pas dans NP-Complete. En fait, personne n'a jamais encore prouvé ce fait : c'est peut-être même dans P, mais dans ce cas on ne l'a pas encore remarqué. https://en.wikipedia.org/wiki/Intege...ate_of_the_art

Sinon, il ne suffit pas d'écrire un circuit logique pour multiplier deux nombres, puis d'égaler la sortie au nombre à factoriser ? Ensuite, tu peux facilement convertir toutes ces formules booléennes en SAT-3.

[Pecose]

Sinon, il ne suffit pas d'écrire un circuit logique pour multiplier deux nombres, puis d'égaler la sortie au nombre à factoriser ? Ensuite, tu peux facilement convertir toutes ces formules booléennes en SAT-3.

Tu pourrait me donner un exemple simple? Comment faire exactement avec le nombre 10 par exemple?

[Pecose]

Apparemment, il faut utiliser un algo qui s'appelle Rho de Pollard mais j'ai pas bien compris comment il fonctionne et le lien qu'on peut en faire avec SAT.

Sinon, j'ai trouvé ça :
https://cs.stackexchange.com/questio...zation-example
J'ai pas compris. C'est quoi 2k-bit?
Y a moyen de vulgariser un peu plus ?

[Flodelarab]

Bonjour

bit = binary digit = chiffre binaire.
La phrase dit simplement que quand on multiplie 2 nombres de k chiffres, le produit est long de 2k chiffres. Ce que tu savais déjà avec les chiffres décimaux : 999*99=98901 (3 + 2 = 5)

[Pecose]

Ok, merci pour cette réponse.
Du coup j'en reviens au point de départ, comment on fait?