A hierarquia entra em colapso?

Sabemos que a hierarquia não colapso ( para todos os )? $\mathsf{TC^0}$ $\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ $d$

A entrada Zoo para $\mathsf{TC^0}$ menciona apenas a separação entre as profundidades 2 e 3.

Também existe uma referência padrão para o fato de que a hierarquia $\mathsf{AC^0_d}$ não ?

cc.complexity-theory reference-request complexity-classes circuit-complexity bounded-depth Kaveh
fonte

Uma pergunta relacionada seria: quantas funções distintas existem em

A C_{d}^{0}

$AC_d^0$ /

T C_{d}^{0}

$TC_d^0$ ? Um limite inferior razoável dessas quantidades responderia às suas perguntas. Também uma prova de aperto no lema de comutação de Hastad talvez respondesse à sua segunda pergunta.

MCH

Para a segunda pergunta, acredito que foi comprovada pela primeira vez no artigo STOC '83 da Sipser "Conjuntos de Borel e complexidade do circuito" . Isso apenas fornece limites inferiores super-polinomiais. Os primeiros limites exponenciais inferiores foram dados por Yao, posteriormente aprimorados por Håstad.

Robin Kothari

@MCH, você quis escrever

T C_{d}^{0} / A C_{d}^{0}

$\mathsf{TC^0_d}/\mathsf{AC^0_d}$ ? Ou você quer dizer o número de classes de equivalência de problemas nas

T C_{d}^{0}

$\mathsf{TC^0_d}$ wrt

A C_{d}^{0}

$\mathsf{AC^0_d}$ ?

Kaveh

O que quero dizer é muito simples: quantas funções distintas a classe de circuitos de tamanho representa? (Podemos estimar o número de circuitos com muita facilidade, mas devemos ter cuidado para que alguns deles possam calcular a mesma função.) Depois de mostrar que essa quantidade cresce com , está pronto.

A C_{d}^{0}

$AC_d^0$

s

$s$

d

$d$

MCH

@Dilworth, não uniforme. A contagem parece não funcionar, caso contrário, como observei abaixo, poderíamos separar de que está aberto.

T C^{0}

$\mathsf{TC^0}$

N C^{1}

$\mathsf{NC^1}$

Kaveh

Respostas:

Não conhecemos limites inferiores bons (ou seja, um limite superpolinomial para um idioma em ) para circuitos de limite de profundidade 2 (pesos ilimitados). Os circuitos da profundidade 3 construídos a partir dos portões majoritários, ou seja, contêm essa classe e, portanto, também não sabemos limites bons para essa classe. $\mathsf{NEXP}$ $\mathsf{TC}^0_3$

Kristoffer Arnsfelt Hansen
fonte

Isso responde à minha pergunta. Obrigado Kristoffer.

Kaveh

Como escrevi no comentário acima, mesmo que não se saiba que um problema no NEXP esteja fora do TC , ainda não é possível que a hierarquia não uniforme do TC seja adequada por meio de um argumento de contagem no limite inferior?

_{2}^{0}

$^0_2$

^{0}

$^0$

Dilworth

Além disso, posso perguntar, como isso é consistente com os limites inferiores exponenciais conhecidos em TC e a separação dos circuitos de limiar de profundidade 3 e profundidade 2, conforme relatado no zoológico de complexidade? Estou esquecendo de algo?

_{2}^{0}

$_2^0$

Dilworth

@ Dilworth, acho que é porque é definido usando Maioria e não Limiar.

Kaveh

Hmm .. o que você quer dizer com precisão? Isso está relacionado à observação feita por Kristoffer sobre "pesos ilimitados"?

Dilworth

Se não estou , parece que provar que a hierarquia não colapso é pelo menos tão difícil quanto separar de : $\mathsf{TC^0_d}$ $\mathsf{NC^1}$ $\mathsf{TC^0}$

Vamos denotar o problema de avaliação de fórmula booleana pelo . está completo para em . $BFE$ $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0}$

Por Manindra Agrawal, Eric Allender e Steven Rudich, " Reduções na complexidade do circuito: um teorema de isomorfismo e um teorema de lacuna ", 1999, o está completo para em . $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0_2}$

Suponha . Então para alguns . Portanto, . O que significa que . $\mathsf{NC^1}=\mathsf{TC^0}$ $BFE \in \mathsf{TC^0_d}$ $d$ $\mathsf{NC^1} \subseteq \mathsf{TC^0_{d+2}}$ $\mathsf{TC^0} \subseteq \mathsf{TC^0_{d+2}}$

Então, para todos temos $d$

$\mathsf{TC^0} \not\subseteq \mathsf{TC^0_d}$ implica e . $\mathsf{NC^1} \not\subseteq \mathsf{TC^0_{d+2}}$ $BFE \notin \mathsf{TC^0_d}$

Kaveh
fonte