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

14

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?P.NP.

Mike G.
źródło

Odpowiedzi:

9

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 .qnpq=nnpq

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).

Realz Slaw
źródło
3

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

Jeśli wówczas każdy problem w N P, w tym faktoring, będzie miał algorytm wielomianowy.P=NPNP

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.

Kaveh
źródło
tylko dla wyjaśnienia dla PO: w wersji faktoringu opartej na wspólnej decyzji jest „czy liczba ma współczynnik Y taki, że 1 < Y < K ”, gdzie X i K są wprowadzane. certyfikat jest po prostu liczbą Y spełniającą warunek. problemu decyzyjnego można użyć do faktycznego przeszukania binarnego na K, dopóki nie zostanie znaleziony pojedynczy właściwy współczynnik X, a następnie powtórzony na X / YXY1<Y<KXKYKXX/Y .
Sasho Nikolov,