Resultados de inicialização que realmente iniciam

9

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 Π{BFE,WS5,W5STCONN} . Suponha que para cada c>1 existem infinitamente muitos dN tal que TC0 circuitos de profundidade d necessidade mais do que n1+cd fios para resolver o problema Π . Então, para qualquer d0,kNΠTC0d0nkTC0NC1

Teorema. [Gupta et al., FOCS'13] Suponha que o cálculo da permanente exija 3 circuitos aritméticos de profundidade maior que nΩ(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(n2ϵ)

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.AAAA

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

Lwins
fonte
2
Impulsionar (falando livremente: "se você tem um aluno fraco em PAC, você tem um aluno em PAC") se encaixaria na conta?
Clement C.
@ClementC. Certo. O seu comentário me faz lembrar de alguns resultados fundamentais em criptografia, como, “one-way funções implicam famílias de função pseudo-aleatórios”
Lwins

Respostas:

10

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)TIME(nc)c>1TIME(n)TIME(n1+ϵ)ϵ>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(n1+ϵ)TIME(n)=TIME(nc)c

Ryan Williams
fonte
11
Esse é um exemplo adorável! IIRC, o teorema da hierarquia de tempo não determinístico é provado dessa maneira no início (por Cook?).
Lwins
11
Isso é mais ou menos verdade. Em uma aplicação típica do argumento acima, podemos aplicá-lo apenas um número "constante" de vezes; Mostras de Cook como aplicá-la um número "ilimitado" de vezes
Ryan Williams
5

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.

Yonatan N
fonte
4

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

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}n2n1+1

Bjørn Kjos-Hanssen
fonte
3

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 .CC

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

Clemente C.
fonte