Wie kann P =? NP verbessern die Ganzzahlfaktorisierung

Question

Wenn $ { sf p} $ tatsächlich gleich $ { sf np} $ ist, wie würde dies unsere Algorithmen verbessern, um die Ganzzahlen schneller zu berücksichtigen. Mit anderen Worten, welche Art von Einsicht würde diese Tatsache uns das Verständnis der Ganzzahlfaktorisierung besser geben?

Answer 1

Wenn $ p = np $, und wir haben einen Algorithmus, der das lösen kann K-sa Problem in der Polynomzeit, dann kann die Ganzzahlfaktorisierung einfach auf k-sat reduziert werden, indem Factoring als Problem in k-sat beschrieben wird.

Im Wesentlichen funktioniert es wie folgt: Sie erstellen jeweils eine Reihe von Variablen, die die Bits von $ P $ und $ Q $ und $ n $ repräsentieren. Dann formulieren Sie das k-sa-Problem als $ p*q = n $. Da $ n $ bekannt ist, können Sie diese Werte festlegen. Anschließend beschreibt eine zufriedenstellende Aufgabe ein gültiges $ p $ und $ q $. Um die Multiplikation in K-SAT zu beschreiben, können Sie jeden der bekannten Multiplikationsalgorithmen verwenden und den logischen Schaltkreis in k-sa beschreiben. Weitere Informationen zur Reduzierung der Faktorierung auf k-sat finden Sie unter hier.

Was das Verständnis von Factoring besser betrifft, würde dies wahrscheinlich mehr Forschung erfordern und den magischen Algorithmus analysieren (der NP-Complete-Probleme in der deterministischen Polynomzeit lösen kann) und möglicherweise auf die Integer-Factoring-Formulierung von K-SAT-Problem (was offensichtlich hat Eine sehr spezifische Struktur, abhängig vom verwendeten Multiplikationsalgorithmus).

Answer 2

Das Entscheidungsproblem für die Faktorierung beträgt $ mathsf {np} $ und das Factoring kann in deterministischer Polynomzeit darauf reduziert werden.

Wenn $ mathsf {p} = mathsf {np} $ $ dann wird jedes Problem in $ mathsf {np} $ einschließlich Factoring einen Polynomzeitalgorithmus haben.

Beachten Sie, dass die am bekanntesten deterministischen/probabilistischen Algorithmen für die Faktorierung der Exponentialzeit eine große Verbesserung wäre. Um ein Gefühl davon zu bekommen, sollten Sie eine 2000 -Bit -Zahl berücksichtigen. Man kann seit dem Urknall länger dauern als die ganze Zeit, der andere kann in einigen Millisekunden antworten.