La hiérarchie

$\mathsf{TC^0}$ $\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ $d$

L'entrée Zoo pour $\mathsf{TC^0}$ ne mentionne que la séparation entre la profondeur 2 et 3.

Existe-t-il également une référence standard pour le fait que la hiérarchie $\mathsf{AC^0_d}$ ne s'effondre pas?

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

Une question connexe serait: combien de fonctions distinctes y a-t-il dans

A C_{d}^{0}

$AC_d^0$ /

T C_{d}^{0}

$TC_d^0$ ? Une limite inférieure raisonnable sur ces quantités répondrait à vos questions. Une preuve de l'étanchéité du lemme de commutation de Hastad répondrait peut-être à votre deuxième question.

MCH

Pour la deuxième question, je pense qu'elle a été prouvée pour la première fois dans le document STOC '83 de Sipser "Ensembles de Borel et complexité des circuits" . Cela ne donne cependant que des bornes inférieures super-polynomiales. Les premières bornes inférieures exponentielles ont été données par Yao, améliorées plus tard par Håstad.

Robin Kothari

@MCH, vouliez-vous écrire

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

$\mathsf{TC^0_d}/\mathsf{AC^0_d}$ ? Ou voulez-vous dire le nombre de classes d'équivalence de problèmes dans les réductions de

T C_{d}^{0}

$\mathsf{TC^0_d}$ rapport à

A C_{d}^{0}

$\mathsf{AC^0_d}$ ?

Kaveh

Ce que je veux dire est très simple: combien de fonctions distinctes la classe de circuits de taille représenter? (Nous pouvons estimer le nombre de circuits très facilement mais nous devons faire attention à ce que certains d'entre eux puissent calculer la même fonction.) Une fois que vous montrez que cette quantité croît avec , vous avez terminé.

A C_{d}^{0}

$AC_d^0$

s

$s$

d

$d$

MCH

@Dilworth, non uniforme. Le comptage ne semble pas fonctionner, sinon comme je l'ai noté ci-dessous, nous pourrions alors séparer de qui est ouvert.

T C^{0}

$\mathsf{TC^0}$

N C^{1}

$\mathsf{NC^1}$

Kaveh

Réponses:

Nous ne connaissons aucune bonne borne inférieure (c'est-à-dire, disons, une borne inférieure superpolynomiale pour un langage dans ) pour les circuits de seuil de profondeur 2 (poids illimités). Les circuits de profondeur 3 construits à partir de portes majoritaires, c'est-à-dire contiennent cette classe, et donc nous ne connaissons pas non plus de bonnes limites inférieures pour cette classe. $\mathsf{NEXP}$ $\mathsf{TC}^0_3$

Kristoffer Arnsfelt Hansen
la source

Cela répond à ma question. Merci Kristoffer.

Kaveh

Comme je l'ai écrit dans le commentaire ci-dessus, même si un problème dans NEXP n'est pas connu pour être en dehors de TC , n'est-il pas encore possible que la hiérarchie non uniforme TC soit correcte via un argument de comptage borne inférieure?

_{2}^{0}

$^0_2$

^{0}

$^0$

Dilworth

En outre, puis-je demander, comment cela est-il cohérent avec les limites inférieures exponentielles connues sur TC et la séparation de la profondeur 3 des circuits de seuil de profondeur 2, comme indiqué dans le zoo de la complexité? Suis-je en train de manquer quelque chose?

_{2}^{0}

$_2^0$

Dilworth

@Dilworth, je pense que c'est parce qu'il est défini en utilisant Majority not Threshold.

Kaveh

Hmm .. que voulez-vous dire précisément? Est-ce lié à la note de Kristoffer sur les «poids illimités»?

Dilworth

Si je ne me trompe pas, il semble que prouver que la hiérarchie ne s'effondre pas est au moins aussi difficile que de séparer de : $\mathsf{TC^0_d}$ $\mathsf{NC^1}$ $\mathsf{TC^0}$

Notons le problème d'évaluation de formule booléenne par . est terminé pour sous réductions. $BFE$ $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0}$

Par Manindra Agrawal, Eric Allender et Steven Rudich, " Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem ", 1999, est complet pour sous réductions. $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0_2}$

Supposons que . Puis pour certains . Par conséquent . Ce qui signifie 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}}$

Donc , pour tout , nous avons $d$

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

Kaveh
la source