É possível usar restrições aleatórias para obter um limite inferior para ?

Existem vários resultados conhecidos do tamanho do circuito com base em restrições aleatórias e no Switching Lemma . $\mathsf{AC^0}$

Podemos desenvolver um resultado do Switching Lemma para provar um tamanho inferior para os circuitos (semelhante às provas do limite inferior para )? $\mathsf{TC^0}$ $\mathsf{AC^0}$

Ou existe algum obstáculo inerente ao uso dessa abordagem para provar os limites inferiores de ? $\mathsf{TC^0}$

Os resultados das barreiras, como as Provas Naturais, dizem alguma coisa sobre o uso de técnicas semelhantes ao Switching Lemma para provar limites inferiores? $\mathsf{TC^0}$

cc.complexity-theory circuit-complexity lower-bounds boolean-functions Jeigh
fonte

Você está familiarizado com a prova de alternar o lema para ?

A C^{0}

$\mathsf{AC^0}$

Jul12

Li o capítulo sobre limites inferiores do circuito do livro de Arora. Em primeiro lugar, transforme qualquer cirtuit de profundidade constante em um circuito sem portas NOT com camadas AND-OR intercaladas e, em segundo lugar, usando o Switching Lemma switch nesta duas camadas, finalmente obtemos um topo de circuito e o segundo nível é o mesmo portão AND (ou OR) assim, podemos privar o circuito de uma camada, reduzindo a profundidade do circuito.

266

Entretanto, não é simples que o caso booleano observar a saída de um gate quando fixamos vários valores de entradas (no caso booleano, corrigimos sobre raiz quadrada n de entradas). AND gate e OR gate é uma versão extrema dos portões do limiar e é muito fácil observar a influência das restrições.

265

A idéia por trás da técnica de restrições aleatórias é que um atingido por uma restrição aleatória se torne mais simples (de fato constante) com probabilidade diferente de zero, mantendo variáveis livres suficientes. Ao contrário de e gates, um único portão atingido por uma restrição aleatória ainda computaria um portão em entradas de tamanho menor e não se tornará mais simples.

A C^{0}

$\mathsf{AC^0}$

\land

$\land$

\lor

$\lor$

\mod p

$\mod p$

\mod p

$\mod p$

Kaveh

Observe também que as restrições aleatórias e o Switching Lemma são um dos principais exemplos de provas naturais. De qualquer forma, espero que um especialista em complexidade de circuitos publique uma resposta mais abrangente. ps: Tomei a liberdade de reescrever a pergunta, fique à vontade para reverter se você não gostar da minha edição.

26412 Kaveh

Respostas:

É realmente possível fazer uso de restrições aleatórias para provar limites mais baixos para circuitos de limiar.

Em particular, nas compensações de tamanho e profundidade de papel para circuitos de limite , Impagliazzo, Paturi e Saks usam restrições aleatórias para provar um limite inferior do superliner (no número de fios) para circuitos de limite de profundidade constante que calculam a função de paridade.

Com relação à comprovação de limites inferiores superpolinomiais para circuitos , então sim, o conceito de prova natural é relevante, uma vez que existem construções de geradores de funções pseudo-aleatórias em . $\mathsf{TC}^0$ $\mathsf{TC}^0$

Kristoffer Arnsfelt Hansen
fonte

Veja também o artigo recente de Daniel Kane e Ryan Williams, Limites inferiores do fio super-linear e do portão super-quadrático para os circuitos de limiares de profundidade 2 e 3 (STOC 2016).

Ryan descreve o artigo da seguinte forma (a seguinte descrição é retirada de sua página inicial):

Damos uma função explícita em para a qual toda a maioria dos circuitos de limiar linear de profundidade e dois (com pesos ilimitados) precisa de cerca de portas e fios simultaneamente. Também mostramos que a função de Andreev (computável por um circuito majoritário de profundidade três tamanho ) requer que aproximadamente o mesmo limite inferior do fio e da porta seja computado com circuitos de limiar linear de profundidade dois. Uma ferramenta importante é o Lemma de Littlewood-Offord, que usamos para analisar o efeito de restrições aleatórias nas entradas de circuitos de limiares de baixa profundidade. $\mathsf{PP}$ $n^{1.5}$ $n^{2.5}$ $O(n)$

Yuval Filmus
fonte