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?
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?
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.
Zasadniczo działa w następujący sposób: Tworzysz grupę zmiennych, z których każda reprezentuje bity 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 .
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.
Jeśli wówczas każdy problem w N P, w tym faktoring, będzie miał algorytm wielomianowy.
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.