Czy możemy szybko wygenerować idealnie jednolicie mod 3 lub rozwiązać problem NP?

Szczerze mówiąc, nie wiem zbyt wiele o tym, jak generowana jest liczba losowa (komentarze są mile widziane!), Ale załóżmy następujący model teoretyczny: Możemy uzyskać liczby całkowite jednolicie losowe z a naszym celem jest wyprowadza liczbę całkowitą jednolicie losową z [1,3].$[1,2^n]$

Oto proste rozwiązanie, którego oczekiwany czas działania jest wielomianowy. Odrzuć (i prawdopodobnie także ) z aby liczba pozostałych liczb całkowitych była podzielna przez , abyśmy mogli wziąć z wygenerowanej liczby całkowitej. Jeśli otrzymamy odrzucony numer, generujemy kolejny numer, dopóki nie otrzymamy odrzuconego numeru.$2^n$$2^n-1$$[1,2^n]$$3$$\bmod 3$

Ale co, jeśli chcemy zakończyć z pewnością w czasie wielomianowym? Z powodu problemów z podzielnością problem staje się nierozwiązywalny. Zastanawiam się jednak, czy możemy rozwiązać następujące problemy.

Załóżmy, że możemy generować liczby całkowite jednolicie losowe z $[1,2^n]$ i otrzymujemy trudny obliczeniowo problem. Naszym celem jest wyprowadzenie liczby całkowitej równomiernie losowej z [1,3] lub rozwiązanie trudnego problemu.

W tym przypadku trudnym problemem może być faktoring liczby całkowitej, rozwiązanie instancji SAT lub coś podobnego. Na przykład możemy zdekodować permutację jednokierunkową w następujący sposób, jeśli otrzymamy (i załóżmy, że jest parzyste): Jeśli dla naszego losowego ciągu , to weź , jeśli , to weź . Wreszcie, jeśli , to skończymy, ponieważ . (Jeśli jest nieparzyste, to działa coś podobnego, wystarczy sprawdzić również, czy i odjąć jeśli .)f f ( x ) n f ( r ) < f ( x ) f ( r ) mod 3 f ( r ) $f$$f(x)$$n$$f(r)<f(x)$$f(r) \bmod 3$ f ( x ) f ( r ) - 1 mod 3 f ( r ) = f ( x ) r = x n f ( r + 1 ) = f ( $f(r)>f(x)$$f(r)-1\bmod 3$$f(r)=f(x)$$r=x$$n$) 2 f ( r ) > f ( x $f(r+1)=f(x)$$2$$f(r)>f(x)$

Podsumowanie odpowiedzi. Emil Jeřábek pokazał, że jeśli nie będziemy w stanie generować idealnie jednorodnie, możemy rozwiązać każdy pojedynczy problem wyszukiwania z TFNP, a także z PPA-3. Z drugiej strony, daniello pokazało, że nie możemy rozwiązać problemów NP-zupełnych w powyższy sposób, chyba że NP = co-NP.

Jako odpowiedź na odpowiedź domotorp uważam, że możemy rozwiązać problemy z wyszukiwaniem NP, spełniając następujące ograniczenia:

1. liczba rozwiązań jest znana i niepodzielna przez ; lub,$3$

2. liczba rozwiązań jest wielomianowo ograniczona (ale nie znana z góry).

W przypadku 1. możemy zastosować proste wypełnienie, aby zredukować do następującego przypadku:

• Rozwiązania pochodzą z , gdzie jest parzyste.[ 0 , 2 m - 1 ) $[0,2^{m-1})$$m$

• Liczbę rozwiązań spełnia .s s ≡ $s$$s\equiv1\pmod3$

• Wszelkie dwa rozwiązania są w odległości co najmniej od siebie. (Powiedz, że wszystkie są podzielne przez ).4 $4$$4$

Zauważ, że . Tak więc, możemy rozwiązać ten problem, wybierając losowo , a przy użyciu protokołu podobny jak w mojej odpowiedzi na unikalnych rozwiązań jeśli (w wyniku podziału on krótszy o jeden dla każdego rozwiązania ), i wyprowadzanie jeśli .3 ∣ 2 m - s a ∈ [ 0 , 2 m ) a ∈ [ 0 , 2 $3\mid 2^m-s$$a\in[0,2^m)$ - s ) { 0 , 1 , 2 } 0 s 0 a ∈ [ 2 m - s , 2 m$a\in[0,2^m-s)$$\{0,1,2\}$$0$$s$$0$$a\in[2^m-s,2^m)$

Dla 2. załóżmy najpierw, że liczba rozwiązań jest znana . Jak w /cstheory//a/37546 , niech będzie największą potęgą dzielącą , tak że . Rozważmy problem wyszukiwania, którego rozwiązaniami są sekwencje tak że , a każdy jest rozwiązaniem pierwotnego problemu. Z jednej strony pierwotny problem sprowadza się do nowego. Z drugiej strony liczba rozwiązań nowego problemu wynosi , tzn. Nie dzieli się przezs ≤ p ( n ) 3 k 3 s 3 ∤ ($s\le p(n)$$3^k$$3$$s$3 k )y0,…,$3\nmid\binom s{3^k}$ 3 k - 1 y0<y1<⋯<y 3 k - 1 yi ($y_0,\dots,y_{3^k-1}$$y_0<y_1<\dots<y_{3^k-1}$$y_i$3 k )$\binom s{3^k}$$3$i znany. Tak więc skończymy o 1.

Teraz, jeśli liczba rozwiązań jest ograniczona przez , ale nie jest znana, uruchamiamy protokół powyżej razy ( ) równolegle dla każdego możliwego wyboru i:p ( n ) 2 ℓ 2 ℓ ≥ p ( n ) 1 ≤ s ≤ 2 $p(n)$$2^\ell$$2^\ell\ge p(n)$$1\le s\le2^\ell$

• jeśli którykolwiek z wątków zwróci rozwiązanie pierwotnego problemu, jeden taki przekazujemy do wyniku;

• jeśli wszystkie wątki zwracają elementy , wyprowadzamy .r 1 , … , r 2 ℓ ∈{0,1,2}(r1+r2+⋯+r 2 ℓ )mod$r_1,\dots,r_{2^\ell}\in\{0,1,2\}$$(r_1+r_2+\dots+r_{2^\ell})\bmod3$

Uwarunkowane drugim zdarzeniem, jest równomiernie rozłożone w ponieważ jest prawdziwą liczbą rozwiązań pierwotnego problemu, podczas gdy inne są niezależne od , stąd cała suma jest również równomiernie rozłożona .r s { 0 , 1 , 2 } s r i r $r_s$$\{0,1,2\}$$s$$r_i$$r_s$

Będę używał liczb zaczynających się od zamiast , ponieważ uważam, że jest to bardziej naturalne.0 $0$$1$

Oto dwie klasy problemów, które możemy rozwiązać w ten sposób:

1. Funkcje w TFNP (tzn. Problemy z wyszukiwaniem NP o wartości pojedynczej wartości)

   (Uogólnia to przykład za pomocą permutacji jednokierunkowych. Obejmuje on w szczególny sposób problemy decyzyjne z .)$\mathrm{UP\cap coUP}$

   Konfiguracja polega na tym, że mamy predykat czasu wielomianowego i wielomian taki, że dla każdego długości istnieje unikalne długości takie, że trzyma. Zadaniem obliczeniowym jest, biorąc , znaleźć .R ( x , y ) p ( n $R(x,y)$$p(n)$ x n y m = p ( n ) R ( x , y ) x $x$$n$$y$$m=p(n)$$R(x,y)$$x$$y$

   Teraz założę, że wlog, że jest parzyste, więc . Algorytm polega na generowaniu równomiernie losowego i wynikum 2 m ≡ $m$( mod3 ) y ∈ [ 0 , 2 m$2^m\equiv 1\pmod3$$y\in[0,2^m)$

   • y R ( x , y $y$ (jako rozwiązanie problemu wyszukiwania), jeśli ;$R(x,y)$

   • y - y ′ { 0 $y-y'$ (jako losowy element ), jeśli , i ; 1 , 2 } y - y ′ ∈ { 1 , 2 } R ( x , y ′$\{0,1,2\}$$y-y'\in\{1,2\}$$R(x,y')$

   • y mod 3 { 0 , 1 , 2 } y ′ ∈ { y , y - 1 , y - 2 } R ( x , y ′$y\bmod3$ (jako losowy element ), jeśli nie rozwiązuje .$\{0,1,2\}$$y'\in\{y,y-1,y-2\}$$R(x,y')$

   Gdyby nie było rozwiązania problemu wyszukiwania, losowe wybory dałyby i razy, a razy (jeszcze jeden). Jeśli jednak rozwiązuje problem wyszukiwania, majstrowaliśmy przy elementach (które uderzyły we wszystkie trzy klasy reszt), tak że wytwarzają tylko reszty i , co wyrównuje przewagę . (Zakładam tutaj wlog, że .)2 m 1 $2^m$$1$$2$ ( 2 m - 1 ) / 3 0 ( 2 m$(2^m-1)/3$$0$ 2 ) / 3 y $(2^m+2)/3$$y$ , r + 1 , y + 2 1 2 0 r < 2 m - $y,y+1,y+2$$1$$2$$0$$y<2^m-2$

2. Problemy z wyszukiwaniem PPA-$3$

   Wygodnym sposobem na zdefiniowanie PPA- jest to, że jako problemy z wyszukiwaniem NP wielu można zredukować do następujących rodzajów problemów. Mamy stałą funkcję czasu wielomianowego i wielomian , tak że dla dowolnego wejścia długości indukowane odwzorowanie ograniczone do danych wejściowych długości jest funkcją spełniającą dla każdego . Zadanie to jest, biorąc pod uwagę , znaleźć fixpoint z : .3 f ( x , y ) p ( n ) x $3$$f(x,y)$$p(n)$$x$$n$ f x ( y ) = f ( x , y ) y $f_x(y)=f(x,y)$$y$ = p ( n ) f x : [ 0 , 2 m ) → [ 0 , 2 m ) f x ( f x ( f x ( y ) ) $m=p(n)$$f_x\colon[0,2^m)\to[0,2^m)$= y y x y f x f x ( y ) = $f_x(f_x(f_x(y)))=y$$y$$x$$y$$f_x$$f_x(y)=y$

   Możemy rozwiązać to w następujący sposób: zadając długości , generujemy losowe długości i wyprowadzamyx n y m = p ( n $x$$n$$y$$m=p(n)$

   • y f $y$ jeśli jest to punkt ;$f_x$

   • w przeciwnym razie , i są odrębnymi elementami. Możemy oznaczyć je jako pomocą , a dane wyjściowe takie, że .y f x ( y ) f x ( f x ( y ) $y$$f_x(y)$$f_x(f_x(y))$ { y , f x ( y ) , f x ( f x ( y ) ) } = { y 0 , y 1 , y 2 } y 0 < y 1 < y 2 i ∈ { 0 , 1 , $\{y,f_x(y),f_x(f_x(y))\}=\{y_0,y_1,y_2\}$$y_0<y_1<y_2$} y = y $i\in\{0,1,2\}$$y=y_i$

   To wynika z definicji, co daje równomierne rozprowadzenie w , ponieważ nie fixpoint „y pochodzi z trójek.{ 0 , 1 , 2 } $\{0,1,2\}$$y$

Pokażę dla zapisu, że powyższy problem jest równoważny z kompletnym problemem Papadimitriou dla PPA- , ponieważ klasa ta jest w większości pomijana w literaturze. Problem wspomniano w Buss, Johnson: „Dowody zdań i redukcje między problemami wyszukiwania NP”, ale nie podają równoważności. W przypadku PPA podobny problem (LONELY) podano w Beame, Cook, Edmonds, Impagliazzo i Pitassi: „Względna złożoność problemów wyszukiwania NP”. Nie ma nic specjalnego w , poniższy argument działa mutatis mutandis na każdą nieparzystą liczbę pierwszą.3 $3$$3$

Twierdzenie: Następujące problemy z wyszukiwaniem NP są wielokrotnie wielokrotne redukowane względem siebie:

1. Biorąc pod uwagę obwód reprezentujący dwudzielny niekierowany wykres i wierzchołek którego stopnia nie można podzielić przez , znajdź inny taki wierzchołek.( A ∪ B , E ) u ∈ A ∪ B $(A\cup B,E)$$u\in A\cup B$$3$

2. Biorąc pod uwagę obwód reprezentujący ukierunkowany wykres i wierzchołek którego bilans stopni (tj. Out-stop minus in-stop) nie jest podzielny przez , znajdź inny taki wierzchołek.( V , E ) u ∈ V $(V,E)$$u\in V$$3$

3. Biorąc pod uwagę obwód obliczający funkcję tak, że , znajdź punkt stały .f : [ 0 , 2 n ) → [ 0 , 2 n ) f 3 = i d$f\colon[0,2^n)\to[0,2^n)$$f^3=\mathrm{id}$$f$

Dowód:

$1\le_p2$ jest oczywiste, ponieważ wystarczy skierować krawędzie od lewej do prawej.

2 ≤ p 1 A B V A = { x A : x ∈ V } B = { x B : x ∈ V } x → y { x A , y B } 1 { x B , y A } - 1 stopień ( x A ) = - deg ( x B ) x $2\le_p1$ : Najpierw stwórzmy ważony wykres dwustronny. Niech i będą kopiami : , . Dla każdej oryginalnej krawędzi wstawiamy krawędź o wadze i krawędź o wadze . To sprawia, że równa się równowadze stopni na oryginalnym wykresie. Jeśli jest danym wierzchołkiem równowagi , dodajemy dodatkową krawędź o masie$A$$B$$V$$A=\{x^A:x\in V\}$$B=\{x^B:x\in V\}$$x\to y$$\{x^A,y^B\}$$1$$\{x^B,y^A\}$$-1$$\deg(x^A)=-\deg(x^B)$$x$$u$b ≢ 0( mod3 ) { u A , u B } b deg ( u A ) = 2 b ≢ $b\not\equiv0\pmod3$$\{u^A,u^B\}$$b$, więc , a . będzie naszym wybranym wierzchołkiem.( mod3 ) deg ( u B ) = 0 u $\deg(u^A)=2b\not\equiv0\pmod3$$\deg(u^B)=0$$u^A$

Aby wykres był zwykłym nieważonym wykresem niekierowanym, najpierw zmniejszamy wszystkie wagi modulo i upuszczamy wszystkie krawędzie o wadze . Pozostawia to tylko krawędzie odważników i . Te ostatnie można zastąpić odpowiednimi gadżetami. Na przykład, zamiast ważenia krawędzi , uwzględniamy nowe wierzchołki , dla , z krawędziami , , , , : to powoduje, że3 0 1 2 2 { x A , y B } w A i z B i i = 0 , … , 3 { x A , y B } { x A , z B i } { w A i , y B } { w A i , z B i } { w A $3$$0$$1$$2$$2$$\{x^A,y^B\}$$w_i^A$$z_i^B$$i=0,\dots,3$$\{x^A,y^B\}$$\{x^A,z^B_i\}$$\{w^A_i,y^B\}$$\{w^A_i,z^B_i\}$ , z B ( i + 1 ) mod 4 }deg(w A i )=deg(z B i )=35≡$\{w^A_i,z^B_{(i+1)\bmod4}\}$$\deg(w_i^A)=\deg(z_i^B)=3$I przyczynia do a .( mod3 ) x A i $5\equiv2\pmod3$$x^A$$y^B$

$3\le_p2$ : Załóżmy, że dla uproszczenia jest nawet tak, że . Konstruujemy ukierunkowany wykres na w następujący sposób:n 2 n ≡ $n$( mod3 ) V = [ 0 , 2 n$2^n\equiv1\pmod3$$V=[0,2^n)$

• Uwzględniamy krawędzie i dla każdego .$3x+1\to3x$$3x+2\to3x$$x<2^n/3-1$

• Jeśli jest orbitą nie będącą punktem stałym , uwzględniamy krawędzie od i .$x_0<x_1<x_2$$f$$x_0\to x_1$$x_0\to x_2$

Wybrany wierzchołek będzie . Pierwsza klauzula przyczynia się do równowagi lub do każdego wierzchołka . Podobnie druga klauzula przyczynia się do równowagi lub do wierzchołków, które nie są . Zatem, zakładając, że nie jest już punktem stałym, to rzeczywiście jest to niezrównoważony moduł , a każdy inny niewyważony wierzchołek modułu jest punktem stałym .$u=2^n-1$$1$$-2\equiv1\pmod3$$\ne u$$-1$$2\equiv-1\pmod3$$u$$3$$3$$f$

$1\le_p3$ : Możemy założyć, że z parzystą, a dany wierzchołek ma stopień .$A=B=[0,2^n)$$n$$u\in A$$\equiv2\pmod3$

Możemy skutecznie oznaczać krawędzie występujące wierzchołkiem jako , gdzie . W ten sposób staje się podzbiorem , które utożsamiamy z . Definiujemy funkcję na w następujący sposób.$y\in B$$(y,j)$$j<\deg(y)$$E$$[0,2^n)\times[0,2^n)$$[0,2^{2n})$$f$$[0,2^n)\times[0,2^n)$

• Na dopełnieniu : dla każdego i tak, że , tworzymy , , . Również , , dla . to punkt i punkty dla każdego którego stopnia nie można podzielić przez .$E$$y\in B$$j$$\deg(y)\le 3j<2^n-1$$f(y,3j)=(y,3j+1)$$f(y,3j+1)=(y,3j+2)$$f(y,3j+2)=(y,3j)$$f(3i,2^n-1)=(3i+1,2^n-1)$$f(3i+1,2^n-1)=(3i+2,2^n-1)$$f(3i+2,2^n-1)=(3i,2^n-1)$$3i<2^n-1$$(2^n-1,2^n-1)$$3-(\deg(y)\bmod 3)$$(y,i)$$y\in B$$3$

• W : dla każdego naprawiamy wydajne wyliczanie jego krawędzi incydentów , gdzie . Kładziemy , , dla . Zrezygnowano punktów dla każdego wierzchołka , którego stopnia nie jest podzielna przez .$E$$x\in A$$(y_0,j_0),\dots,(y_{d-1},j_{d-1})$$d=\deg(x)$$f(y_{3i},j_{3i})=(y_{3i+1},j_{3i+1})$$f(y_{3i+1},j_{3i+1})=(y_{3i+2},j_{3i+2})$$f(y_{3i+2},j_{3i+2})=(y_{3i},j_{3i})$$i<\lfloor d/3\rfloor$$\deg(x)\bmod3$$x\in A$$3$

Odkąd , dwie z jego krawędzi zdarzeń zostały pominięte; przekształcamy je w kolejny cykl , używając jako trzeciego punktu. Pozostałe punkty pozostają jako punkty stałe . Z założenia każdy z nich da rozwiązanie (1).$\deg(u)\equiv2\pmod3$$f$$(2^n-1,2^n-1)$$f$

Jeśli potrafisz idealnie wygenerować mod LUB rozwiązać SAT (lub jakikolwiek inny problem NP-zupełny), to . W szczególności rozważ idealny generator / solver, gdy otrzymasz formułę SAT .$3$$NP = coNP$$\phi$

Niech będzie maksymalną liczbą losowych bitów generowanych przez generator na wejściach o rozmiarze . Ponieważ generator działa w czasie wielomianowym, jest wielomianem. Ponieważ nie jest podzielne przez , musi istnieć pewna sekwencja co najwyżej rzutów monetą, która sprawi, że generator wygeneruje (poprawną) odpowiedź dla . Zatem jeśli jest niezadowalająca, istnieje zestaw podrzucanych monet, które powodują, że generator mówi, że jest niezadowalająca. Jeśli jest zadowalające, generator nigdy nie będzie błędnie twierdził, że$\ell(n)$$n$$\ell(n)$$2^{\ell(n)}$$3$$\ell(n)$$\phi$$\phi$$\phi$$\phi$$\phi$jest niezadowalający, bez względu na monety. Wykazaliśmy zatem, że język niezadowalających wzorów znajduje się w , co oznacza, że . $UNSAT$$NP$$NP = coNP$

Oto więc rozszerzenie argumentu Emila, które pokazuje, że problemy z wyszukiwaniem, w których liczba rozwiązań wynosi 1, 2 lub 4 (nie musimy wiedzieć, które) można rozwiązać w powyższy sposób. Podaję to jako odpowiedź, ponieważ jest to zbyt długo na komentarz i mam nadzieję, że ktoś mądrzejszy ode mnie może udowodnić, że w rzeczywistości liczba rozwiązań może być czymś niepodzielnym przez 3.

Powiedz, że losowy ciąg jest zbliżony do rozwiązania (tj. Do dla którego utrzymuje), jeśli jeden z , lub utrzymuje. (Dla prostoty, załóżmy, że i , nie są rozwiązaniami) w roztworze Emila, było wystarczające do wytworzenia losowy ciąg i wyjściowe poza tym, że lokalnie skrzypacz wokół w roztworach; Nie wchodzę w szczegóły, zobacz jego odpowiedź. Wystarczy nam, że jeśli jest blisko rozwiązania, możemy zabić dowolną liczbę$r$$y$$R(x,y)$$R(x,r)$$R(x,r+1)$$R(x,r+2)$$y=0$$y=1$$r$$r\bmod 3$$r$$\bmod 3$przez ewentualne wyjście rozwiązania tak, że dla reszty r funkcja r mod 3 daje idealnie jednolitą liczbę mod 3 .$r$$r\bmod 3$$\bmod 3$

Załóżmy teraz, że liczba rozwiązań wynosi 1 lub 2 dla dowolnego x . Generujemy dwa losowe ciągi o długości n : r 1 i r 2 . Jeśli przynajmniej jedno z nich nie jest bliskie rozwiązaniu, wyprowadzamy r 1 + r 2 mod 3 . Dla uproszczenia załóżmy, że n jest nawet tak, że mamy dodatkowe 0, jeśli właśnie to zrobiliśmy, a także załóżmy, że jeśli są dwa rozwiązania, są daleko. Jeśli oba r 1 i r 2 są zbliżone do tego samego rozwiązania, bawimy się, aby zabić 0. Jeśli r 1 i $x$$n$$r_1$$r_2$$r_1+r_2\bmod 3$$n$$r_1$$r_2$$r_1$2 są bliskie różnym rozwiązaniom, wtedy jeśli r 1 < r 2 , bawimy się, aby zabić 1, a jeśli r 1 > r 2 , bawimy się, aby zabić 2. W ten sposób, jeśli jest tylko jeden rozwiązanie, zabijamy dokładnie jedno 0, a jeśli są dwa rozwiązania, zabijamy dwa 0, i jeden 1 i jeden 2.$r_2$$r_1<r_2$$r_1>r_2$

Ten argument nie może być rozszerzony na 3 rozwiązania, ale może dotyczyć 4, i odtąd będę bardzo szkicowy. Wygeneruj cztery losowe ciągi, r 1 , r 2 , r 3 , r 4 i wyślij r 1 + r 2 + r 3 + r 4 mod 3, chyba że wszystkie są blisko rozwiązania. Ponownie załóżmy, że jest dodatkowe 0, a rozwiązania są zawsze daleko. W przypadku wszystkich r I „s są zbliżone do tego samego rozwiązania, możemy bawić się, aby zabić 0. Jeśli trzy z r $r_1,r_2,r_3,r_4$$r_1+r_2+r_3+r_4 \bmod 3$$r_i$$r_i$„s są zbliżone do tego samego rozwiązania, które jest mniejsze niż w roztworze, do którego czwarty R i jest blisko, możemy pobawić się wokół zabić 1. W przypadku trzech z R I ” s są blisko tego samego rozwiązania, które jest większe niż rozwiązaniem, które czwarty R i jest blisko, możemy pobawić się wokół zabić 2. Jeżeli wszystkie R i „s są zbliżone do innego rozwiązania, możemy zabić trzy 0-tych. Poprawność jednego i dwóch rozwiązań jest podobna do poprzedniego przypadku. W przypadku czterech rozwiązań zauważmy, że zabijamy cztery + trzy 0, sześć 1 i sześć 2.$r_i$$r_i$$r_i$$r_i$

Myślę, że rozumowanie ostatniego akapitu można rozszerzyć na dowolną ograniczoną liczbę rozwiązań, których nie da się podzielić przez 3 za pomocą algebry. Bardziej interesujące pytanie dotyczy tego, czy istnieje protokół działający dla dowolnej liczby rozwiązań.