Kompletny wariant faktoringu NP.

Książka Arory i Baraka przedstawia faktoring jako następujący problem:

$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$

Dodają, w dalszej części rozdziału 2, że usunięcie faktu, że jest liczbą pierwszą, sprawia, że ten problem NP jest kompletny, chociaż nie jest to związane z trudnością faktoryzacji liczb. Wygląda na to, że może być obniżka z SUBSETSUM, ale utknąłem, szukając go. Czy jest tu więcej szczęścia? $p$

EDIT 01 marca: Bounty jest na -completeness dowodu przy użyciu deterministycznego Karp (lub Cooka) redukcji. $NP$

cc.complexity-theory np-hardness factoring

— Michaël Cadilhac
źródło

@turkistany: FWIW, uważam za zły styl, aby umieścić kursywę w NP, a zarówno zły styl, jak i zły LaTeX, aby wprowadzić go w tryb matematyczny (ponieważ odstępy między literami różnią się).

— Michaël Cadilhac

@ Michaël, Przepraszamy, przywrócono oryginalny styl. Podnieciło mnie twoje pytanie :)

— Mohammad Al-Turkistany,

Nieco bardziej kompletny opis: na stronie 63 książki piszą: Alon i Kilian (w komunikacji osobistej) wykazali, że w definicji języka Faktoring w przykładzie 2.3 warunek, że czynnik p jest liczbą pierwszą, jest konieczny, aby uchwycić problem faktoringu, ponieważ bez tego warunku ten język jest NP-kompletny (z powodów niemających nic wspólnego z twardością faktorowania liczb całkowitych).

— MS Dousti,

Oczywiście szukałem artykułu Alona i Kiliana zawierającego „faktoring” i „NP-zupełny”. Nie znalazłem żadnego (wydaje mi się, że jest to w pewnym sensie naturalne). :(

— Tsuyoshi Ito

@Michael I rzeczywiście jak rendering klasach

zamiast NP. Nie?

N P

$\mathsf{NP}$

— Suresh Venkat

Odpowiedzi:

To nie do końca odpowiedź, ale jest blisko. Poniżej znajduje się dowód na to, że problem jest trudny NP przy losowych redukcjach.

Istnieje oczywisty związek z sumą podzbioru, który brzmi: załóżmy, że znasz czynniki : , , , . Teraz chcesz znaleźć podzbiór z takie, że $N$ $p_1$ $p_2$ $\ldots$ $p_k$ $S$ $p_1$ $\ldots$ $p_k$

\log L. \leq \sum_{p_{ja} \in S.} \log p_{ja} \leq \log U .

$\displaystyle \log L \leq \sum_{p_i \in S} \log p_i \leq \log U.$

Problem z próbą wykorzystania tego pomysłu do pokazania, że problem jest NP-trudny, polega na tym, że jeśli masz problem z podzbiorem o liczbach , , , , niekoniecznie możesz znaleźć liczby pierwsze w czasie wielomianowym, takie jak że (gdzie przez , mam na myśli w przybliżeniu proporcjonalne do). To jest prawdziwy problem, ponieważ, ponieważ podzbiorem sumy nie jest silnie NP-zupełny, trzeba znaleźć te dla dużych liczb całkowitych . $t_1$ $t_2$ $\ldots$ $t_k$ $\log p_i \propto t_i$ $\propto$ $\log p_i$ $t_i$

Załóżmy teraz, że wymagamy, aby wszystkie liczby całkowite w problemie sumy podzbioru zawierały się w przedziale od do i że suma wynosi około $t_1$ $\ldots$ $t_k$ $x$ $x(1+1/k)$ . Problem sumy podzbiorów nadal będzie NP-zupełny, a każde rozwiązanie będzie sumąliczb całkowitych. Możemy zmienić problem z całkowitymi do liczb rzeczywistych, jeśli pozwolimy wynosić odi $\frac{1}{2}\sum_i t_i$ $k/2$ $t'_i$ $t_i$ i zamiast wymagać, aby suma była dokładnie, wymagamy, aby zawierała się międzyi $t_i+\frac{1}{10k}$ $s$ $s$ . Aby to zrobić, musimy jedynie podać nasze liczby na okołowięcej bitów precyzji. Zatem, jeśli zaczniemy od liczb zbitamii możemy podać liczby rzeczywistedo okołobitów precyzji, możemy przeprowadzić naszą redukcję. $s + \frac{1}{10}$ $4 \log k$ $B$ $\log p_i$ $B + 4 \log k$

Teraz z wikipedii (przez komentarzu Hsien-Chih za poniżej), liczba liczb pierwszych między i jest , więc jeśli tylko wybierać numery losowo w tym zakresie, a przetestuj je pod kątem pierwotności, z dużym prawdopodobieństwem uzyskaj liczbę pierwszą w czasie wielomianowym. $T$ $T+ T^{5/8}$ $\theta(T^{5/8}/\log T)$

Teraz spróbujmy redukcji. Powiedzmy, że nasz są wszystkie bitów. Jeśli weźmiemy o długości bitów, to możemy znaleźć doskonałą pobliżu z bitów precyzją. W ten sposób, możemy wybrać tak, że z precyzją $t_i$ $B$ $T_i$ $3B$ $p_i$ $T_i$ $9/8B$ $T_i$ $\log T_i \propto t_i$ bitów. To pozwala nam znaleźć tak że z precyzją $9/8\, B$ $p_i \approx T_i$ $\log p_i \propto t_i$ bitów. Jeśli podzbiór tych liczb pierwszych mnoży się do wartości zbliżonej do wartości docelowej, istnieje rozwiązanie pierwotnych problemów z sumą podzbiorów. Dlatego pozwalamy , odpowiednio dobrać i , i mamy losową redukcję z sumy podzbioru. $9/8\,B$ $N=\Pi_i p_i$ $L$ $U$

— Peter Shor
źródło

Nie rozumiem redukcji. Aby problem sumy podzbiorów był NP-zupełny, liczba musi być podana w postaci binarnej. Jeśli chcemy liczb całkowitych, których logarytmy są zbliżone do liczb w wystąpieniu problemu sumy podzbioru, potrzebujemy wykładniczo wielu cyfr. Jak sobie z tym poradzić?

— Tsuyoshi Ito

@Peter: Założenie teorii liczb nazywa się hipotezą Craméra , która stwierdza, że

, gdzie

jest n-tą liczbą pierwszą. Zobacz także pierwszą lukę w artykule w celach informacyjnych.

p_{n + 1} - p_{n} = O (\log^{2} n)

$p_{n+1} - p_n = O(\log^2 n)$

p_{n}

$p_n$

— Hsien-Chih Chang 8 之

@Peter: Tak, ta wersja założenia została udowodniona dla

wystarczająco dużej. Pierwszy wynik tego rodzaju pokazuje Hoheisel, a najlepszy wynik dzięki Wikipedii to dzieło Bakera, Harmana i Pintza , o

(ponieważ dotyczy prawdopodobieństwa 1)

T

$T$

α = 0.525

$\alpha = 0.525$

c_{1} = \infty

$c_1 = \infty$

c_{2} = 1

$c_2 = 1$

— Hsien-Chih Chang 張顯之

Właśnie się z tym spotkałem. Powinienem zauważyć, że nie wiem, jaki był oryginalny dowód Kilian-Alon. Moją jedyną wiedzą na temat dowodu jest komunikacja z Nogą, który nie pamiętał szczegółów oryginalnego dowodu, a zrekonstruowany przez niego dowód był właśnie tym. Zauważ, że można go również opisać jako redukcję deterministyczną przy pewnych założeniach teoretycznych o dużej liczbie (np. Że liczba pierwsza występuje w dowolnym przedziale postaci [x, x + polylog (x)]).

— Boaz Barak

Właśnie rozmawiałem z Joe Kilianem. Powiedział, że dowód, że on i Alon wymyślili, dotyczył losowych redukcji zerowego błędu. O ile mu wiadomo, redukcja deterministyczna jest wciąż otwarta, chyba że podejmie się jakieś teoretyczne założenie, jak już powiedział Boaz Barak.

— Timothy Chow,

Myślę, że jest to powiązane z twierdzeniem PCP (w szczególności ). $NP = PCP[O(\log{n}), O(1)]$

Fragment gazety Madhu :

... Pojęcie, że weryfikator może wykonywać dowolne wielomianowe obliczenia czasowe, znacznie wzbogaca klasę twierdzeń i dowodów i zaczyna oferować wysoce nietrywialne metody dowodzenia twierdzeń. (Jedną z bezpośrednich konsekwencji jest to, że możemy założyć, że twierdzenia / dowody / twierdzenia / argumenty są ciągami binarnymi i zrobimy to odtąd.) Na przykład załóżmy, że mamy twierdzenie (powiedzmy hipoteza Riemanna) i powiedzmy, że wierzymy, że dowód, który mieściłby się w artykule na 10 000 stron. Perspektywa obliczeniowa mówi, że biorąc pod uwagę i ten związany (10 000 stron), można skutecznie obliczyć trzy dodatnie liczby całkowite z $A$ $A$ $N, L, U$ $L \leq U \leq N$ tak, że jest prawdziwe wtedy i tylko wtedy, gdy jest dzielnik między i . Liczby całkowite , i będą dość długie (być może ich napisanie zajmie milion stron), ale można je wyprodukować niezwykle wydajnie (w czasie krótszym niż czas potrzebny na wydrukowanie wszystkich liczb całkowitych przez drukarkę, co z pewnością wynosi najwyżej dzień lub dwa). (Ten konkretny przykład oparty jest na wyniku spowodowanym osobistą komunikacją Joe Kiliana ) ... $A$ $N$ $L$ $U$ $N$ $L$ $U$

... daleko poza moimi umiejętnościami teorii złożoności :-)

— Marzio De Biasi
źródło

To tylko kolejna formuła, że ten problem jest NP-zupełny.

— Marc Bury,

@Marc ... mmm ... Myślę, że to znaczy:

jest NP-zupełny ponieważ wielomian redukcja z problem NP-zupełnyKRÓTKIM DOWODUistnieje ...

{⟨ L, U, N ⟩ | (\exists p \in {L, \dots, U}) [p | N]}

$\{\langle L, U, N \rangle \;|\; (\exists p \in \{L, \ldots, U\})[p | N]\}$

— Marzio De Biasi

Problem KRÓTKICH DOWODÓW w dokumencie jest prawie taki sam jak problem ograniczonego zatrzymania. Zmniejszenie z problemu KRÓTKICH DOWODÓW byłoby najprawdopodobniej tak niechlujne jak typowy dowód kompletności NP dla SAT, a zatem jest mało prawdopodobne, aby dowód kompletności NP tego problemu ze znalezieniem czynnika przez Kiliana skonstruował redukcję z KRÓTKI DOWÓD PROBLEM bezpośrednio.

— Tsuyoshi Ito

Jest to nieformalny skuteczny pomysł deterministycznej redukcji (i może być niepełny):

Fractran to kompletny język programowania Turinga. Odpowiednio zdefiniowane ograniczony wersja programów Fractran należy sprowadzić do języka $\{\langle L, U, M \rangle \;|\; (\exists \text{ a positive integer } p \in \{L, \ldots, U\})[p | M]\}$

Na przykład, ograniczonym wersja może zapytać, czy liczba całkowita jest wytwarzany w sekwencji wyjściowego Fractran programu w określonej liczbie etapów (działy) (czyli ). $M$ $M=N_j * F_i$

— Mohammad Al-Turkistany
źródło