Jak P =? NP zwiększa rozkład na czynniki całkowite

Jeśli faktycznie jest równe N P , w jaki sposób poprawiłoby to nasze algorytmy do szybszego obliczania liczb całkowitych. Innymi słowy, jaki wgląd dałby nam ten fakt w lepszym zrozumieniu faktoryzacji liczb całkowitych?${\sf P}$${\sf NP}$

Jeśli , a mamy algorytm, który może rozwiązać problem k-SAT w czasie wielomianowym, wówczas rozkład na czynniki całkowite można po prostu zredukować do k-SAT, opisując faktoring jako problem w k-SAT.$P=NP$

Zasadniczo działa w następujący sposób: Tworzysz grupę zmiennych, z których każda reprezentuje bity $p$ i , i n . Następnie formułujesz problem k-SAT jako p ∗ q = n . Ponieważ n jest znane, możesz ustawić te wartości. Następnie zadowalające przypisanie opisuje prawidłowe p i q . Aby opisać mnożenie w k-SAT, możesz użyć dowolnego znanego algorytmu mnożenia i opisać jego obwód logiczny w k-SAT. Aby uzyskać więcej informacji na temat zmniejszania faktoringu do k-SAT, zobacz tutaj .$q$$n$$p*q=n$$n$$p$$q$

Jeśli chodzi o lepsze zrozumienie faktoringu, prawdopodobnie wymagałoby to więcej badań i analizy magicznego algorytmu (który może rozwiązać problemy NP-zupełne w deterministycznym czasie wielomianowym) i być może specjalizowanie go w formułowaniu liczb całkowitych problemu k-SAT (który oczywiście ma bardzo specyficzna struktura, w zależności od zastosowanego algorytmu mnożenia).

Problemem decyzyjnym dla faktoringu jest i faktoring można do niego zredukować w deterministycznym czasie wielomianowym.$\mathsf{NP}$

Jeśli wówczas każdy problem w N P, w tym faktoring, będzie miał algorytm wielomianowy.$\mathsf{P}=\mathsf{NP}$$\mathsf{NP}$

Zauważ, że najbardziej znane algorytmy deterministyczne / probabilistyczne do faktoringu zajmują obecnie czas wykładniczy, więc wielomianowy algorytm czasowy stanowiłby wielką poprawę. Aby to poczuć, rozważ faktoring 2000-bitowej liczby. Jedna może potrwać dłużej niż cały czas od Wielkiego Wybuchu, druga może odpowiedzieć w ciągu kilku milisekund.