Wyniki ładowania początkowego, które naprawdę się ładują

Istnieje rodzaj wyników w TCS, zwykle nazywany wynikami ładowania początkowego . Ogólnie rzecz biorąc, ma formę

Jeśli twierdzenie zachowuje, to twierdzenie zachowuje.$A$$A'$

gdzie $A$a to zdania, które wyglądają podobnie, a wydaje się „słabsze” niż , dlatego nazywamy ten typ wyników. Podam kilka konkretnych przykładów:$A'$$A$$A'$

Twierdzenie. [Chen and Tell, STOC'19] Napraw każdy problem$\Pi \in \{\mathsf{BFE,W_{S_5},W5STCONN}\}$ . Załóżmy, że dla każdego$c>1$ istnieje nieskończenie wiele $d\in \mathbb{N}$ takie, że $\mathcal{TC}^0$ obwody głębokości $d$ potrzebuję więcej niż $n^{1+c^{-d}}$ przewody do rozwiązania problemu $\Pi$. Więc dla każdego$d_0,k \in \mathbb{N}$, $\Pi$ nie może być rozwiązany przez $\mathcal{TC}^0$ obwody głębokości $d_0$ i $n^k$ druty i dlatego $\mathcal{TC}^0 \subsetneq \mathcal{NC}^1$.

Twierdzenie. [Gupta i in., FOCS'13] Załóżmy, że obliczenie permanentu wymaga głębokości$3$ obwody arytmetyczne o rozmiarze większym niż $n^{\Omega(\sqrt{n})}$, ponad polami charakterystycznymi $0$. Zatem obliczenie stałej wymaga obwodów arytmetycznych o wielkości wielobiegunowej, a zatem obowiązuje hipoteza Valianta.

Cóż, bardziej znany, ale nie tak odpowiedni przykład pochodzi z drobnoziarnistej złożoności:

Twierdzenie. [Backurs and Indyk, STOC'15] Jeśli możemy obliczyć EDYCJA ODLEGŁOŚCI w$O(n^{2-\epsilon})$ czasu (w modelu RAM), wtedy otrzymamy solver SAT szybciej niż jakikolwiek obecnie.

Aktualizacja. (10 lipca 2019 r.) Przykład odległości edycji może być nieco mylący. Zobacz odpowiedź Ryana na „standardowy” przykład.

Jak mogłeś sobie wyobrazić, (według mojej najlepszej wiedzy) wszystkie wyniki tego typu zostały udowodnione poprzez zastosowanie środka przeciwnego (wziąłem ten środek przeciwny w edytorze dystansowym). W pewnym sensie są to wszystkie wyniki algorytmiczne.

Zwykle są dwa sposoby zrozumienia wyniku ładowania. 1. Musimy tylko udowodnić$A$ a następnie zastosuj wynik, jeśli chcemy to udowodnić $A'$; 2. Dowodzenie$A$może być trudne, ponieważ z góry uważamy to za dowód$A'$ trudny.

Problem polega na tym, że jeden (a dokładniej ja ) może nie być optymistą i przyjąć pierwsze zrozumienie, jeśli mimo wszystko nie ma pozytywnego zastosowania wyników bootstrap! Więc moje pytanie brzmi

Czy znamy jakikolwiek wynik ładowania początkowego $A$ jest udowodnione?

Klasycznym wynikiem możliwym do udowodnienia za pomocą ładowania początkowego (i mającym zastosowanie do udowodnienia prawdziwych dolnych granic) jest to, że w każdym modelu obliczeniowym, w którym mamy $TIME(n) \neq TIME(n^c)$dla jakiejś stałej$c > 1$tak naprawdę mamy $TIME(n) \neq TIME(n^{1+\epsilon})$dla każdego $\epsilon > 0$.

Chodzi o to, że jeśli $TIME(n) = TIME(n^{1+\epsilon})$, możemy wielokrotnie zastosować argument dopełniający, aby uzyskać $TIME(n) = TIME(n^c)$dla każdej stałej$c$. Możesz nawet użyć takiego argumentu, aby nieco poprawić znane twierdzenia dotyczące hierarchii czasu w różnych przypadkach.

Nie jestem pewien, czy to się liczy, ponieważ wszystko pochodzi z tego samego papieru, ale w pierwszym przejściu Craiga Gentry'ego przy całkowicie homomorficznym szyfrowaniu opartym na idealnych sieciach , najpierw pokazuje, że aby zbudować schemat FHE, wystarczy zbudować „nieco” schemat szyfrowania homomorficznego z pewną właściwością (jego obwód deszyfrowania jest płytszy niż głębokości, w których obwód może szyfrować). Następnie, przy dużym nakładzie pracy, pokazuje, jak zbudować taki nieco homomorficzny schemat szyfrowania.

Ostatni dowód Huanga na $A'$, hipoteza wrażliwości, polegająca na udowodnieniu $A$wiadomo, że to sugeruje. Zobacz blog Aaronsona:

Z pionierskiej pracy Gotsmana i Liniala w 1992 r. Wiadomo było, że aby udowodnić hipotezę wrażliwości, wystarczy udowodnić następującą jeszcze prostszą hipotezę kombinatoryczną $A$:

Niech S będzie dowolnym podzbiorem n-wymiarowego hipersześcianu boolowskiego, $\{0,1\}^n$, który ma rozmiar $2^{n-1}+1$. Następnie musi być punkt w S z co najmniej ~ sąsiadami w S.

Jedną z rzeczy, które przychodzą na myśl w obliczeniowej teorii uczenia się, jest wzmocnienie . Głównie:

W ustawieniach PAC, jeśli masz słaby uczeń w klasie $\mathcal{C}$ (tj. coś, co robi „tylko lepiej” niż losowe zgadywanie), wtedy otrzymujesz (mocnego) ucznia dla klasy $\mathcal{C}$.

Zazwyczaj jest to wykorzystywane przez uzyskanie słabego ucznia.