Resultados de arranque que realmente arrancan

Hay un tipo de resultados en TCS que generalmente se llaman resultados de arranque . En general, es de la forma

Si la proposición $A$ cumple, entonces la proposición $A'$ cumple.

donde $A$ y $A'$ son proposiciones que se parecen, y $A$ es aparentemente "más débil" que $A'$ , que es la razón por la que nombramos este tipo de resultados. Permítanme dar algunos ejemplos concretos:

Teorema. [Chen y Tell, STOC'19] Solucione cualquier problema $\Pi \in \{\mathsf{BFE,W_{S_5},W5STCONN}\}$ . Suponga que para cada $c>1$ existen infinitos $d\in \mathbb{N}$ modo que $\mathcal{TC}^0$ circuitos de profundidad T C 0$d$ necesitan más de $n^{1+c^{-d}}$ cables para resolver el problema $\Pi$ . Entonces por cualquier $d_0,k \in \mathbb{N}$ ,$\Pi$ no puede ser resuelto por$\mathcal{TC}^0$ circuitos de profundidad$d_0$ y$n^k$ alambres, y por lo tanto$\mathcal{TC}^0 \subsetneq \mathcal{NC}^1$ .

Teorema. [Gupta et al., FOCS'13] Suponga que calcular el permanente requiere profundidad- $3$ circuitos aritméticos de tamaño mayor que $n^{\Omega(\sqrt{n})}$, sobre campos de la característica$0$. Luego, calcular el permanente requiere circuitos aritméticos de tamaño superpolinomial y, por lo tanto, se cumple la Conjetura de Valiant.

Bueno, un ejemplo más famoso pero no tan apropiado proviene de la complejidad de grano fino:

Teorema. [Backurs e Indyk, STOC'15] Si podemos calcular la DISTANCIA DE EDICIÓN en tiempo $O(n^{2-\epsilon})$ (en el modelo RAM), obtendremos un solucionador SAT más rápido que cualquiera que exista actualmente.

Actualizar. (10 de julio de 2019) El ejemplo de edición de distancia puede ser un poco confuso. Consulte la respuesta de Ryan para obtener un ejemplo "estándar".

Como habrás imaginado, (hasta donde sé ), todos los resultados de este tipo se prueban tomando el contrapositivo (he tomado el contrapositivo en la distancia de edición). Entonces, en cierto sentido, todos estos son resultados algorítmicos.

Por lo general, hay dos formas de comprender un resultado de arranque. 1. Solo necesitamos probar $A$ y luego aplicar el resultado, si queremos probar $A'$ ; 2. Probar $A$ puede ser difícil porque a priori pensamos que es difícil probar $A'$ .

¡El problema es que, uno (o más exactamente, I ) puede ser apenas optimista y comprenderlo por primera vez, si no existe un uso positivo de los resultados de bootstrap después de todo! Entonces mi pregunta es

¿Sabemos ningún resultado bootstrapping en la que $A$ se demuestra?

Un resultado clásico demostrable mediante bootstrapping (y aplicable para probar límites inferiores reales) es que en cualquier modelo computacional donde tenemos $TIME(n) \neq TIME(n^c)$ para alguna constante $c > 1$ , de hecho tener $TIME(n) \neq TIME(n^{1+\epsilon})$ , por cada $\epsilon > 0$ .

La idea es que si $TIME(n) = TIME(n^{1+\epsilon})$ , podemos aplicar un argumento de relleno repetidamente para obtener $TIME(n) = TIME(n^c)$ para cada constante $c$ . Incluso puede usar dicho argumento para mejorar ligeramente los teoremas de la jerarquía del tiempo conocidos en varios casos.

No estoy seguro de si esto cuenta porque todo proviene del mismo documento, pero en el primer paso de Craig Gentry en encriptación totalmente homomórfica basada en redes ideales , primero muestra que para construir un esquema FHE, es suficiente construir un "algo esquema de cifrado homomórfico con cierta propiedad (su circuito de descifrado es menos profundo que las profundidades que el circuito puede cifrar). Luego, con mucho trabajo, muestra cómo construir un esquema de cifrado tan homomórfico.

La prueba reciente de Huang de $A'$ , la Conjetura de la sensibilidad, implicó probar que se sabe que una $A$ implica. Ver el blog de Aaronson:

A partir del trabajo pionero de Gotsman y Linial en 1992, se sabía que para probar la Conjetura de la sensibilidad, basta con probar la siguiente conjetura combinatoria $A$ aún más simple :

Sea S cualquier subconjunto del hipercubo booleano n-dimensional, $\{0,1\}^n$ , que tiene un tamaño de $2^{n-1}+1$ . Entonces debe haber un punto en S con al menos ~ nc vecinos en S.

Una cosa que viene a la mente, en la teoría del aprendizaje computacional, es el impulso . Esencialmente:

En la configuración del PAC, si tiene una débil alumno para la clase $\mathcal{C}$ (es decir, haciendo algo "meramente mejor" que adivinar al azar), entonces se obtiene un alumno (fuerte) para la clase $\mathcal{C}$ .

Por lo general, esto se usa para obtener un alumno débil.