Existe-t-il une hypothèse plausible de complexité / cryptographie qui exclut la possibilité que les circuits de taille polynomiale aient des circuits de taille sous-exponentielle (c'est-à-dire avec ϵ < 1 ) à profondeur limitée ( d = O ( 1 )
TC0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd L'entrée Zoo pour TC0TC0\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 AC0dACd0\mathsf{AC^0_d} ne...
Contexte La complexité du circuit est définie comme l'ensemble des familles de circuits (c'est-à-dire des séquences de circuits, une pour chaque taille d'entrée) de profondeur bornée et de taille polynomiale construites à l'aide de fan-in illimités ET, OU et NON.AC0AC0AC^0 La fonction de parité...