Resultados de inicialização que realmente iniciam

Existe um tipo de resultado no TCS geralmente chamado de resultados de inicialização . Em geral, é da forma

Se a proposição $A$ mantém, então a proposição $A'$ mantém.

onde $A$ e $A'$ são proposições que parecem semelhantes, e $A$ é aparentemente "mais fraco" que $A'$ , razão pela qual denominamos esse tipo de resultado. Deixe-me dar alguns exemplos concretos:

Teorema. [Chen e Tell, STOC'19] corrigir qualquer problema $\Pi \in \{\mathsf{BFE,W_{S_5},W5STCONN}\}$ . Suponha que para cada $c>1$ existem infinitamente muitos $d\in \mathbb{N}$ tal que $\mathcal{TC}^0$ circuitos de profundidade $d$ necessidade mais do que $n^{1+c^{-d}}$ fios para resolver o problema $\Pi$ . Então, para qualquer $d_0,k \in \mathbb{N}$$\Pi$$\mathcal{TC}^0$$d_0$$n^k$$\mathcal{TC}^0 \subsetneq \mathcal{NC}^1$

Teorema. [Gupta et al., FOCS'13] Suponha que o cálculo da permanente exija $3$ circuitos aritméticos de profundidade maior que $n^{\Omega(\sqrt{n})}$ , sobre os campos da característica $0$ . O cálculo da permanente requer circuitos aritméticos de tamanho superpolinomial e, portanto, a Conjectura de Valiant se mantém.

Bem, um exemplo mais famoso, mas não tão apropriado, vem da complexidade refinada:

Teorema. [Backurs and Indyk, STOC'15] Se pudermos calcular EDIT DISTANCE no tempo (no modelo RAM), obteremos um solucionador SAT mais rápido do que qualquer outro que exista atualmente.$O(n^{2-\epsilon})$

Atualizar. (10 de julho de 2019) O exemplo da distância de edição pode ser um pouco confuso. Consulte a resposta de Ryan para um exemplo "padrão".

Como você deve ter imaginado, (pelo que eu saiba), todos os resultados desse tipo são comprovados pela tomada do contrapositivo (eu peguei o contrapositivo na distância de edição um). Então, em certo sentido, todos esses são resultados algorítmicos.

Geralmente, existem duas maneiras de entender um resultado de inicialização. 1. Só precisamos provar e aplicar o resultado, se queremos provar ; 2. Proving pode ser difícil porque a priori que acha provando difícil.$A$$A'$$A$$A'$

O problema é que, um (ou mais exatamente, I ) pode ser pouco otimista e entender primeiro, se não houver nenhum uso positivo dos resultados da inicialização! Então minha pergunta é

Conhecemos algum resultado de inicialização em que seja comprovado?$A$

Um resultado clássico que pode ser provado pelo bootstrapping (e aplicável à prova de limites inferiores reais) é que em qualquer modelo computacional em que temos para alguma constante , na verdade temos , para cada .$TIME(n) \neq TIME(n^c)$$c > 1$$TIME(n) \neq TIME(n^{1+\epsilon})$$\epsilon > 0$

A idéia é que, se , podemos aplicar um argumento de preenchimento repetidamente para obter para cada constante . Você pode até usar esse argumento para melhorar levemente os teoremas da hierarquia de tempo conhecidos em vários casos.$TIME(n) = TIME(n^{1+\epsilon})$$TIME(n) = TIME(n^c)$$c$

Não sei se isso conta, porque é tudo do mesmo artigo, mas na primeira passagem de Craig Gentry para criptografia totalmente homomórfica com base em treliças ideais , ele primeiro mostra que, para construir um esquema de FHE, basta construir um "algo esquema de criptografia homomórfica "com uma determinada propriedade (seu circuito de descriptografia é mais raso do que as profundidades que o circuito pode criptografar). Ele então, com muito trabalho, mostra como construir um esquema de criptografia um tanto homomórfico.

A recente prova de Huang de , a Conjectura de Sensibilidade, envolveu provar um conhecido por implicá-lo. Veja o blog de Aaronson:$A'$$A$

Do trabalho pioneiro de Gotsman e Linial em 1992, sabia-se que para provar a conjectura de sensibilidade, basta provar a seguinte conjectura combinatória ainda mais simples :$A$

Seja S qualquer subconjunto do hipercubo booleano n-dimensional, , que tenha tamanho . Então deve haver um ponto em S com pelo menos ~ nc vizinhos em S.$\{0,1\}^n$$2^{n-1}+1$

Uma coisa que vem à mente, na teoria da aprendizagem computacional, é aumentar . Essencialmente:

Na configuração do PAC, se você tem um aluno fraco para a classe (ou seja, algo que está "meramente melhor" do que suposições aleatórias), então você obtém um aluno (forte) para a classe .$\mathcal{C}$$\mathcal{C}$

Normalmente, isso é realmente usado pela obtenção de um aluno fraco.