Dlaczego losowość ma większy wpływ na redukcje niż na algorytmy?

Przypuszcza się, że losowość nie rozszerza potęgi algorytmów wielomianu czasowego, co oznacza, że jest przypuszczalny do utrzymania. Z drugiej strony losowość wydaje się mieć zupełnie inny wpływ na skrócenie czasu wielomianu . Według dobrze znanego wyniku Valiant i Vazirani, redukuje się do poprzez losowe wielomianowe skrócenie czasu. Jest mało prawdopodobne, że redukcja mogłaby zostać poddana derandomizacji, ponieważ dałaby ona , co jest uważane za mało prawdopodobne.${\bf P}={\bf BPP}$$SAT$$USAT$${\bf NP}={\bf UP}$

Zastanawiam się, co może być przyczyną tej asymetrycznej sytuacji: derandomizacja wydaje się całkiem możliwa w probabilistycznych algorytmach wielomianu czasu, ale nie w probabilistycznych wielomianowych redukcjach czasu?

Po pierwsze, pozwól mi skomentować konkretny przypadek redukcji Valiant-Vazirani; Mam nadzieję, że pomoże to wyjaśnić ogólną sytuację.

Redukcję Valiant-Vazirani można przeglądać / definiować na kilka sposobów. Ta redukcja „próbuje” zamapować satysfakcjonującą boolowską formułę na jednoznacznie satysfakcjonującą F ' , a niezadowalającą F na niezadowalającą F ' . Wszystkie formuły wyjściowe są zawsze uzyskiwane przez dalsze ograniczenie F , więc niezadowolenie jest zawsze zachowane. Zmniejszenie może być zdefiniowane albo jako wyprowadzenie pojedynczego F ' , albo jako wyprowadzenie listy F ' 1 , … , F ' t . W tym drugim przypadku „sukces” w przypadku F $F$$F'$$F$$F'$$F$$F'$$F'_1, \ldots, F'_t$ jest zdefiniowany jako mającyco najmniej jedenwyjątkowo satysfakcjonujący F ' i na liście. Nazwij te dwa warianty odpowiednio „redukcją singletonów” i „redukcją listy” (nie jest to standardowa terminologia).$F \in SAT$$F'_i$

Pierwszą kwestią, na którą należy zwrócić uwagę, jest to, że prawdopodobieństwo sukcesu w redukcji singletonu jest dość małe, mianowicie gdzie n jest liczbą zmiennych. Trudności związane z poprawą tego prawdopodobieństwa sukcesu zostały omówione w artykule$\Theta(1/n)$$n$

„Czy prawdopodobieństwo izolacji Valiant-Vazirani można poprawić?” przez Dell i in.

http://eccc.hpi-web.de/report/2011/151/#revision1

Na liście redukcji, prawdopodobieństwo sukcesu może być duża, znaczy z poli ( n ) listy -sized. (Na przykład można po prostu wielokrotnie powtórzyć redukcję singletonu).$1 - 2^{-n}$$(n)$

Teraz nie jest wcale oczywiste ani intuicyjne, że powinniśmy być w stanie bezpośrednio derandomizować redukcję, która ma jedynie prawdopodobieństwo sukcesu . Rzeczywiście, żaden z wyników twardość w stosunku do losowości nie podaje hipotez, na podstawie których możemy to zrobić w tym przypadku. Bardziej prawdopodobne jest, że redukcję listy można derandomizować (z nieco większą listą). Zauważ jednak, że nie oznaczałoby to N P = U P : nasza lista wyjściowa formuł może mieć wiele wyjątkowo satysfakcjonujących formuł, a być może niektóre z wieloma satysfakcjonującymi przypisaniami, i wydaje się beznadziejna próba zdefiniowania wyjątkowo akceptowalnego obliczenia w stosunku do takiego lista. $1/n$$NP = UP$

Nawet gdybyśmy mogli w jakiś sposób dać list-redukcji, w której spełnialna zawsze wywołanego listę F ' 1 , ... , F ' t gdzie większość of the f ' j „y są wyjątkowo spełnialna, nie ma wyraźnego sposób, aby włączyć to pod deterministyczna redukcja singletonu dla izolacji. Prawdziwa trudność bazowy jest to, że nie znam żadnego „operacji przybliżona większością na wzorach wyjątkowym spełnialna”, czyli zmniejszenie R ( F ' 1 , ... , F ' t$F$$F'_1, \ldots, F'_t$$F'_j$$R(F'_1, \ldots, F'_t)$których wynik jest wyjątkowo zadowalający, jeżeli większość jest wyjątkowo satysfakcjonująca, i niezadowalający, jeśli większość F ' j jest niezadowalająca. Wydaje się to również zjawiskiem ogólnym: redukcje generują bardziej złożone obiekty niż algorytmy decyzyjne, a właściwości tych obiektów są trudniejsze do sprawdzenia, dlatego trudniej jest połączyć wiele z tych obiektów w jeden obiekt, który dziedziczy niektóre właściwości większości.$F'_j$$F'_j$

W przypadku Valiant-Vazirani nawet nie wydaje się prawdopodobne przy prawdopodobnych założeniach derandomizacji, że moglibyśmy uzyskać , to znaczy deterministycznie zmniejszyć zadowalające wzory do zadowalających wzorów z ≤ poli ( n ) rozwiązania. Intuicyjnie ten wynika z faktu, że procedura izolacji nie ma pojęcia nawet szorstkiej wielkości zestawu rozwiązań o wzorze F jest przekazywana.$NP = FewP$$\leq$$(n)$$F$

W świecie wyroczni łatwo jest podać przykłady, w których losowość daje nam znacznie więcej mocy. Rozważmy na przykład problem znalezienia zera zrównoważonej funkcji boolowskiej. Algorytm randomizowany osiąga to, że wykorzystuje zapytania ze stałym prawdopodobieństwem sukcesu, podczas gdy dowolny algorytm deterministyczny wymaga co najmniej n / 2 zapytań.$O(1)$$n/2$

Oto kolejna sytuacja, w której podejrzewa się, że randomizacja pomaga. Załóżmy, że chcemy zmaksymalizować monotoniczną funkcję podmodularną w porównaniu z ograniczeniem matroidowym. Istnieją dwa różne algorytmy, które dają przybliżenie , i jest to optymalne w tym modelu dzięki wynikowi Vondráka. Oba algorytmy muszą obliczyć funkcję o postaci E x ∼ X f ( x ) , gdzie $1-1/e$$\mathbb{E}_{x \sim X} f(x)$$X$jest dystrybucją ze wsparciem wykładniczym. Dokładne obliczenie tej funkcji jest zbyt kosztowne, ale można ją aproksymować przez próbkowanie, a wynikiem jest algorytm losowy. W przeciwieństwie do tego, najbardziej znany algorytm deterministyczny algorytm zachłanny, daje przybliżenia.$1/2$

Podobna sytuacja występuje w nieograniczonej maksymalizacji podmodularnej (tutaj funkcja niekoniecznie jest monotoniczna). Niedawna algorytm przełom daje optymalną przybliżenie, ale jego deterministycznej wersji daje tylko 1 / 3 przybliżenia. Tutaj randomizacja objawia się albo dokładnie w taki sam sposób, jak w przypadku monotonicznym, lub (w innej wersji algorytmu) poprzez dokonanie kilku losowych wyborów po drodze.$1/2$$1/3$

Jeden z autorów badań tych przypuszczeń papierowych że jest najlepszy, że algorytm deterministyczny mogą osiągnąć, a my możemy podobnie przypuszczenie, że 1 / 2 jest najlepsza, które mogą być osiągnięte w poprzednim problemie. Jeśli te przypuszczenia są prawdziwe, to jest to bardzo naturalna sytuacja, w której randomizacja jest prawdopodobnie pomocna.$1/3$$1/2$

Ostatnio Dobziński i Vondrák pokazali, jak przekształcić dolne granice wyroczni (dla algorytmów losowych) w wyniki twardości, pod warunkiem, że NP różni się od RP (kluczowym składnikiem jest dekodowanie listy). Powinniśmy wspomnieć, że transformacja opiera się na konkretnej metodzie użytej do udowodnienia dolnych granic wyroczni. Być może prawdą jest, że dolne granice wartości deterministycznej wyroczni również przekładają się na wyniki twardości.

Jednym z powodów może się wydawać dziwne, do ciebie, że wydaje się, że jest bardziej widoczne (lub conjectured) Moc w randomizowanych redukcji z do U P niż w porównywalnym jednym z B P P do P , dlatego może być kusiło by pomyśleć o przypadkowości jako o czymś, co jest albo potężne (albo mało wydajne) niezależnie od tego, do której „maszyny” dodajesz go (jeśli karykaturujemy te klasy złożoności jako klasy wynikające z modeli maszyn).$\mathsf{NP}$$\mathsf{UP}$$\mathsf{BPP}$$\mathsf P$

A jednak istnieją te redukcje różnych mocy. W rzeczywistości zasoby obliczeniowe, takie jak przypadkowość, niekoniecznie mają określoną moc obliczeniową, która jest albo „znacząca”, albo „nieistotna”.

Możemy uznać, że każda klasa złożoności, która jest dla siebie niska - na przykład , P , B P P , B Q P , ⊕ P lub P S P A C E - może być dostosowana do modelu maszynowego, w którym maszyna zawsze ma dobrze zdefiniowany stan, w którym można zadawać pytania w dowolnym momencie, jednocześnie umożliwiając kontynuowanie obliczeń poza pytaniem: w zasadzie dokładnie tak, że maszyna może symulować jeden algorytm jako podprogram dla inne. Maszyna, która wykonuje obliczenia, może nie być szczególnie realistyczna$\mathsf L$$\mathsf P$$\mathsf{BPP}$$\mathsf{BQP}$$\mathsf{\oplus P}$$\mathsf{PSPACE}$jeśli ograniczyć się do praktycznych ograniczeń zasobów ( np  fizycznie wykonalne i zdolny do odpowiedzi produkują w niskiej stopień wielomianu czasu dla problemów będących przedmiotem zainteresowania), ale w przeciwieństwie do klas, takich jak - dla których nie mamy pojęcia, jak niedeterministyczny maszyna może produkować odpowiedź na inny problem w N P i używać odpowiedź w żaden sposób oprócz (powtórzyć) koniunkcyjnej i dysjunktywny redukcji prawda stołu - wyobrażając sobie taką klasę jako wykonany przez maszynę z dobrze zdefiniowanym stanem której możemy dociekać robi nie wprowadzaj nas w błąd.$\mathsf{NP}$$\mathsf{NP}$

Jeśli zajmiemy to stanowisko, możemy zapytać, co się stanie, jeśli zapewnimy tym modelom obliczeniowym dodatkowe udogodnienia, takie jak losowość lub niedeterminizm. (Te dodatkowe ułatwienia niekoniecznie zachowują właściwość interpretacji przez model maszyny, szczególnie w przypadku niedeterminizmu, ale dają początek „nowym” klasom.) Jeśli to dodatkowe ułatwienie daje modelowi więcej mocy, dając początek do klasy C , jest to w rzeczywistości równoważne stwierdzeniu, że istnieje redukcja z C do M za pomocą tej funkcji, np.  losowa redukcja w przypadku losowości.$\mathsf M$$\mathsf C$$\mathsf C$$\mathsf M$

Powodem, dla którego opisuję to w kategoriach klas, które są dla siebie niskie, jest to, że jeśli poważnie traktujemy, że są one „możliwymi modelami obliczeń w innym świecie”, twoje pytanie o losowe redukcje odpowiada temu, że wydaje się, że losowość radykalnie zwiększa moc niektórych modeli, ale nie innych .

Zamiast losowych redukcji z do U P możemy zaobserwować, że istnieje losowa redukcja z całego P H do klasy B P ⋅ ⊕ P - która jest uzyskiwana, jeśli dodasz losowość błędu ograniczonego do ⊕ P - przez Twierdzenie Tody. A twoje pytanie może być postawione jako: dlaczego tak się dzieje ? Dlaczego niektóre maszyny miałyby tak wiele czerpać z losowości, a inne tak mało? W przypadku P H ⊆ B P ⋅ ⊕ P wydaje się, że niedeterminizm modulo-2 pociąga za sobą definicję$\mathsf{NP}$$\mathsf{UP}$$\mathsf{PH}$$\mathsf{BP\cdot\oplus P}$$\mathsf{\oplus P}$$\mathsf{PH} \subseteq \mathsf{BP\cdot\oplus P}$ (zasadniczo moduł kwantyfikatora zliczania 2) katalizuje losowość związaną z błędem ograniczonym (zasadniczo kwantyfikator zliczania z luką obietnicy), aby dać nam ekwiwalent całej nieograniczonej hierarchii egzystencjalnych i uniwersalnych kwantyfikatorów. Ale to nie znaczy, że przypuszczamy, że ⊕ P jest w przybliżeniu tak samo potężny jak cała hierarchia wielomianowa, prawda? Ani zasoby losowości z ograniczonym błędem, ani liczenie modulo-2 nie są uważane za tak potężne. Zauważyliśmy, żerazemte dwa kwantyfikatorysątak potężne.$\mathsf{\oplus P}$$\mathsf{\oplus P}$

Pojawia się również pytanie, czy naprawdę możemy powiedzieć, że losowość jest słaba w wartościach bezwzględnych, w porównaniu do niedeterminizmu: jeśli losowość jest tak słaba i jeśli jesteśmy tak przekonani, że , dlaczego możemy wiązać B P P ⊆ Σ p 2 ∩ Δ p 2 w hierarchii wielomianowej, wykorzystując dwa poziomy nieokreśloności, a co dopiero jeden? Może to jednak wynikać z faktu, że chociaż podejrzewamy, że losowość dodana do prostego obliczania w czasie wielomianowym nie daje dużej mocy, nie mamy pojęcia, jak symulować tę dodatkową moc, wykorzystując jedynie niewielką niedeterminizm tego rodzaju w $\mathsf{BPP} = \mathsf{P}$$\mathsf{BPP} \subseteq \Sigma^{\mathsf p}_2 \cap \Delta^{\mathsf p}_2$ a c o N P . (Oczywiściew teorii złożonościtrudno jest udowodnićcośnietrywialnego; ale toznowutylko stwierdzenie, że te różne rodzaje zasobów są trudne do porównania w skali!)$\mathsf{NP}$$\mathsf{coNP}$

Nie ma mocnego argumentu, który mógłbym uzasadnić, dlaczego tak powinno być, poza stwierdzeniem, że jak dotąd tak jest ; i jeśli uważasz, że nie zapada się, różni się od ⊕ P i że B P P ≈ P , to powinieneś rozważyć możliwość, że udogodnienia takie jak przypadkowość i niedeterminizm mogą mieć moce, które nie są łatwo porównywalne z jedną i które mogą się nawzajem synergizować lub katalizować, aby dać moc obliczeniową, której żaden z nich prawdopodobnie nie miałby sam z siebie. Hipoteza, że B P P = $\mathsf{PH}$$\mathsf{\oplus P}$$\mathsf{BPP} \approx \mathsf{P}$$\mathsf{BPP} = \mathsf{P}$nie jest tak, że „losowość nie ma mocy”, ale sama losowość (a raczej uzupełniona jedynie obliczaniem czasu wielomianowego i przekazana do innego deterministycznego modelu obliczeniowego) nie jest silna. Nie oznacza to jednak, że losowość nie może obejmować mocy, która może być katalizowana przez inne zasoby obliczeniowe.