Wie kann P =? NP verbessern die ganzzahlige Faktorisierung

Wenn tatsächlich gleich N P ist , wie würde dies unsere Algorithmen verbessern, um ganze Zahlen schneller zu faktorisieren. Mit anderen Worten, welche Art von Einsicht würde uns diese Tatsache zum besseren Verständnis der Faktorisierung von ganzen Zahlen verhelfen?${\sf P}$${\sf NP}$

Wenn ist und wir einen Algorithmus haben, der das k-SAT- Problem in Polynomzeit lösen kann, kann die ganzzahlige Faktorisierung einfach auf k-SAT reduziert werden, indem Factoring als Problem in k-SAT beschrieben wird.$P=NP$

Im Wesentlichen funktioniert es wie folgt: Sie erstellen eine Reihe von Variablen, die jeweils die Bits von , q und n darstellen . Dann formulieren Sie das k-SAT-Problem als p ∗ q = n . Da n bekannt ist, können Sie diese Werte einstellen. Dann beschreibt eine befriedigende Zuordnung ein gültiges p und q . Um die Multiplikation in k-SAT zu beschreiben, können Sie einen der bekannten Multiplikationsalgorithmen verwenden und die logische Schaltung in k-SAT beschreiben. Weitere Informationen zur Reduzierung des Factorings auf k-SAT finden Sie hier .$p$$q$$n$$p*q=n$$n$$p$$q$

Ein besseres Verständnis des Factorings würde wahrscheinlich mehr Forschung und Analyse des magischen Algorithmus erfordern (der NP-vollständige Probleme in der deterministischen Polynomzeit lösen kann) und ihn möglicherweise auf die ganzzahlige Factoring-Formulierung des k-SAT-Problems spezialisieren (was offensichtlich der Fall ist) eine sehr spezifische Struktur, abhängig vom verwendeten Multiplikationsalgorithmus).

Das Entscheidungsproblem für das Factoring ist und das Factoring kann in deterministischer Polynomzeit darauf reduziert werden.$\mathsf{NP}$

Wenn dann dann irgendein Problem in N P wird einschließlich Factoring eine Polynomialzeitalgorithmus haben.$\mathsf{P}=\mathsf{NP}$$\mathsf{NP}$

Es ist zu beachten, dass die derzeit bekanntesten deterministischen / probabilistischen Algorithmen zum Faktorisieren exponentielle Zeit benötigen, sodass ein polynomieller Zeitalgorithmus eine große Verbesserung darstellt. Ziehen Sie eine 2000-Bit-Zahl in Betracht, um sich ein Bild davon zu machen. Einer kann länger dauern als die ganze Zeit seit dem Urknall, der andere kann in wenigen Millisekunden antworten.