¿Existe alguna hipótesis plausible de complejidad / criptografía que descarte la posibilidad de que los circuitos de tamaño polinomial tengan circuitos de tamaño subexponencial (es decir, con ϵ < 1 ) de profundidad limitada ( d = O ( 1 ) )?2O ( nϵ)2O(nϵ)2^{O(n^\epsilon)}ϵ <...
TC0TC0\mathsf{TC^0} dTC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd La entrada del zoológico para TC0TC0\mathsf{TC^0} solo menciona la separación entre la profundidad 2 y 3. ¿También hay una referencia estándar para el hecho de que la jerarquía AC0dACd0\mathsf{AC^0_d} no...
Antecedentes Complejidad del circuito se define como el conjunto de familias de circuitos (es decir, secuencias de circuitos, una para cada tamaño de entrada) de profundidad acotada y tamaño polinomial construido utilizando el ventilador sin límites AND, OR y NOT.AC0AC0AC^0 La función de paridad...