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$

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 : p 1 , p 2 , … , p k . Teraz chcesz znaleźć podzbiór S z p 1 ... p k takie, że$N$$p_1$$p_2$$\ldots$$p_k$$S$$p_1$ $\ldots$ $p_k$

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 , t 2 , … , t k , niekoniecznie możesz znaleźć liczby pierwsze w czasie wielomianowym, takie jak że log p i ∝ t i (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 log P I dla dużych liczb całkowitych t I .$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 … t k w problemie sumy podzbioru zawierały się w przedziale od x do x ( 1 + 1 / k ) 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łkowitychk/2. Możemy zmienić problem z całkowitymi do liczb rzeczywistych, jeśli pozwolimyt ' i wynosić odtIiti+$\frac{1}{2}\sum_i t_i$$k/2$$t'_i$$t_i$ i zamiast wymagać, aby suma była dokładnies, wymagamy, aby zawierała się międzysis+$t_i+\frac{1}{10k}$$s$$s$ . Aby to zrobić, musimy jedynie podać nasze liczby na około4logkwięcej bitów precyzji. Zatem, jeśli zaczniemy od liczb zbitamiBi możemy podać liczby rzeczywistelogpido okołoB+4logkbitó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 T + T 5 / 8 jest θ ( T 5 / 8 / log T ) , 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 B bitów. Jeśli weźmiemy T I o długości 3 B bitów, to możemy znaleźć doskonałą p ja pobliżu T I z 9 / 8 B bitów precyzją. W ten sposób, możemy wybrać T i tak, że log T i a t I z precyzją 9 /$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źć p í ≈ T í tak że log p i a t I z precyzją 9 /$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 N = Π i p i , odpowiednio dobrać L i U , i mamy losową redukcję z sumy podzbioru.$9/8\,B$$N=\Pi_i p_i$$L$$U$

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ę A i ten związany (10 000 stron), można skutecznie obliczyć trzy dodatnie liczby całkowite N , L , U z L ≤ U ≤ $A$$A$$N, L, U$$L \leq U \leq N$tak, że jest prawdziwe wtedy i tylko wtedy, gdy N jest dzielnik między L i U . Liczby całkowite N , L i U 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 :-)

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 = N j * f I ).$M$$M=N_j * F_i$