Génération circuit 3SAT pour Integer factorisation exemple

Question

J'ai lu quelque part que 3SAT peut être utilisé pour résoudre Entier factorisation.

Si cela est vrai, quelqu'un pourrait me enseigner un exemple simple de générer le 3SAT en utilisant un petit nombre? Disons que vous donne le numéro 6, puis les facteurs 2 et 3.

Answer 1

Tout d'abord nous réduisons la tâche de factorisation de trouver un facteur (ou montrant qu'il est premier) $ n $. Une fois que nous savons comment faire, on divise $ n $ par un tel facteur et répétez le processus jusqu'à ce que tous les facteurs sont ventilés à des nombres premiers, et cela prend $ O (\ log n) $ étapes.

Soit $ k = \ lceil \ n log_2 \ rceil $ le nombre de bits de $ n $.

Ensuite, nous concevons un circuit multiplication binaire qui accepte deux $ k $ nombre et -bit produit 2k $ $ résultats -bit. La taille du circuit est évidemment polynôme en k $ $.

A la sortie du circuit, nous ajoutons un comparateur 2k $ $ -bit que les rendements true si le résultat est égal à $ et $ n false autrement. Nous ajoutons aussi des comparateurs aux entrées que vérifier que les entrées sont $> 1 $. Ainsi, le circuit combiné prend deux k $ $ -bit nombres et retourne true si elles sont à la fois $> 1 $ et leur produit est égal à $ n $.

Un tel circuit peut être décrit par une formule propositionnelle, donc de cette façon que nous le convertir en SAT .

Enfin, par une procédure standard nous le convertissons de SAT à 3-SAT. Le résultat sera une formule 3-SAT avec 2k $ $ variables propositionnelles. Si elle est satisfiable, les variables propositionnelles vont juste encodent deux facteurs de $ n $. Si c'est insatisfiable cela signifie que $ n $ est premier.