Bootstrapping-Ergebnisse, die wirklich booten

In TCS gibt es eine Art von Ergebnissen, die normalerweise als Bootstrapping-Ergebnisse bezeichnet werden . Im Allgemeinen ist es von der Form

Wenn Satz $A$ gilt, gilt Satz $A'$ .

wobei $A$ und $A'$ Sätze sind, die ähnlich aussehen, und $A$ scheinbar "schwächer" ist als $A'$ , weshalb wir diese Art von Ergebnissen nennen. Lassen Sie mich einige konkrete Beispiele nennen:

Satz. [Chen und Tell, STOC'19] Beheben Sie jedes Problem $\Pi \in \{\mathsf{BFE,W_{S_5},W5STCONN}\}$ . Es sei angenommen , dass für jedes $c>1$ gibt es unendlich viele $d\in \mathbb{N}$ , so dass $\mathcal{TC}^0$ Schaltungen der Tiefe $d$ Notwendigkeit , mehr als $n^{1+c^{-d}}$ Drähte das Problem zu lösen $\Pi$ . Dann für jeden $d_0,k \in \mathbb{N}$$\Pi$$\mathcal{TC}^0$$d_0$$n^k$$\mathcal{TC}^0 \subsetneq \mathcal{NC}^1$

Satz. [Gupta et al., FOCS'13] Angenommen, die Berechnung der bleibenden Karte erfordert Tiefen- Rechenschaltungen mit einer Größe von mehr als über Feldern der Charakteristik . Dann erfordert die Berechnung der bleibenden Karte arithmetische Schaltungen mit Superpolynomgröße, und daher gilt Valiant's Conjecture.$3$$n^{\Omega(\sqrt{n})}$$0$

Nun, ein berühmteres, aber nicht so angemessenes Beispiel stammt aus der feinkörnigen Komplexität:

Satz. [Backurs and Indyk, STOC'15] Wenn wir EDIT DISTANCE in berechnen können (beim RAM-Modell), erhalten wir einen SAT-Solver schneller als einen derzeit vorhandenen.$O(n^{2-\epsilon})$

Aktualisieren. (10. Juli 2019) Das Beispiel für die Bearbeitungsentfernung kann etwas verwirrend sein. In Ryans Antwort finden Sie ein „Standard“ -Beispiel.

Wie Sie sich vielleicht vorgestellt haben, werden (nach meinem besten Wissen) alle Ergebnisse dieses Typs durch die Verwendung des Kontrapositivs bewiesen (ich habe das Kontrapositiv in der Bearbeitungsentfernung eins genommen). In gewissem Sinne sind dies alles algorithmische Ergebnisse.

Normalerweise gibt es zwei Möglichkeiten, ein Bootstrapping-Ergebnis zu verstehen. 1. Wir müssen nur $A$ beweisen und dann das Ergebnis anwenden, wenn wir $A'$ beweisen wollen ; 2. $A$ zu beweisen kann schwierig sein, weil wir es a priori für schwierig halten, $A'$ beweisen .

Das Problem ist, dass einer (oder genauer gesagt ich ) kaum optimistisch sein und das erste Verständnis annehmen kann, wenn es doch keine positive Verwendung von Bootstrap-Ergebnissen gibt! Meine Frage ist also

Kennen wir ein Bootstrapping-Ergebnis, bei dem $A$ bewiesen ist?

Ein klassisches Ergebnis, das durch Bootstrapping bewiesen werden kann (und auf das Beweisen realer Untergrenzen anwendbar ist), ist, dass wir in jedem Rechenmodell, in dem wir $TIME(n) \neq TIME(n^c)$ für eine Konstante $c > 1$ , tatsächlich habe $TIME(n) \neq TIME(n^{1+\epsilon})$ für jedes $\epsilon > 0$ .

Die Idee ist, dass wenn $TIME(n) = TIME(n^{1+\epsilon})$ , wir wiederholt ein Füllargument anwenden können, um $TIME(n) = TIME(n^c)$ für zu erhalten jede Konstante $c$ . Sie können ein solches Argument sogar verwenden, um bekannte Zeithierarchiesätze in verschiedenen Fällen geringfügig zu verbessern.

Ich bin mir nicht sicher, ob dies zählt, da alles aus demselben Artikel stammt, aber in Craig Gentrys erstem Durchgang zur vollständig homomorphen Verschlüsselung auf der Grundlage idealer Gitter zeigt er zunächst, dass es ausreicht, um ein "etwas" zu konstruieren, um ein FHE-Schema zu konstruieren homomorphes "Verschlüsselungsschema mit einer bestimmten Eigenschaft (seine Entschlüsselungsschaltung ist flacher als die Tiefen, die die Schaltung verschlüsseln kann). Dann zeigt er mit viel Arbeit, wie man ein solches etwas homomorphes Verschlüsselungsschema konstruiert.

Huangs jüngster Beweis für $A'$ , die Sensitivitätsvermutung, beinhaltete den Nachweis eines $A$ bekannt ist, dass es dies impliziert. Siehe Aaronsons Blog:

Aus der Pionierarbeit von Gotsman und Linial im Jahr 1992 war bekannt, dass es zum Beweis der Sensitivitätsvermutung ausreicht, die folgende noch einfachere kombinatorische Vermutung $A$ zu beweisen :

Sei S eine beliebige Teilmenge des n-dimensionalen Booleschen Hyperwürfels $\{0,1\}^n$ mit der Größe $2^{n-1}+1$ . Dann muss es in S einen Punkt mit mindestens ~ nc Nachbarn in S geben.

Eine Sache, die in der Theorie des rechnergestützten Lernens in den Sinn kommt, ist das Boosten . Im Wesentlichen:

In der PAC - Einstellung, wenn Sie einen schwachen Lerner für Klasse $\mathcal{C}$ (dh , etwas zu tun „ nur besser“ als zufällige Erraten), dann erhalten Sie einen (starken) Lerner für die Klasse $\mathcal{C}$ .

Typischerweise wird dies tatsächlich verwendet, um einen schwachen Lernenden zu erhalten.