¿

¿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 ) de profundidad limitada ( )? $2^{O(n^\epsilon)}$ $\epsilon<1$ $d = O(1)$

Sabemos que cada función calculable por un circuito puede calcularse por un circuito profundidad de tamaño (usando compuertas AND, OR y NOT, entrada de ventilador sin límites) (por cada hay a y pueden tomarse como ). $\mathsf{NC^1}$ $2^{O(n^\epsilon)}$ $d$ $0 <\epsilon$ $d$ $d$ $O(1/\epsilon)$

La pregunta es:

¿Hay alguna razón que haga improbable la existencia de tales circuitos para circuitos de tamaño polinómico general?

cc.complexity-theory circuit-complexity bounded-depth Kaveh
fuente

Si por tamaño subexponencial quiere decir

(en lugar de

) y por profundidad acotada quiere decir profundidad constante, entonces la paridad no tiene circuitos de profundidad acotada de tamaño subexponencial sin supuestos.

2^{n^{o (1)}}

$2^{n^{o(1)}}$

2^{o (n)}

$2^{o(n)}$

MCH

Debes publicar tu comentario como respuesta. Obtendrá crédito por ello y, si corresponde, puede marcarse como una respuesta aceptada. Esto también evitará que el bot comunitario vuelva a publicar la pregunta periódicamente.

Suresh Venkat

@MCH, actualicé la pregunta para aclarar lo que quiero decir con tamaño subexponencial.

Kaveh

En el caso uniforme, puede decir algo (

implica límites inferiores de tiempo para SAT). Pero en el caso no uniforme, no conocemos límites inferiores fuertes para P / poli, ni límites inferiores fuertes para su definición de circuitos de profundidad constante de tamaño sub-exponencial. Por ejemplo, todavía es posible

T I M E (t) \subseteq Σ_{O (d)} T I M E [n^{1 / d}]

$TIME(t) \subseteq \Sigma_{O(d)}TIME[n^{1/d}]$

E X P^{N P}

$EXP^{NP}$ podría simularse en cualquiera de estas clases. Así que no estoy seguro de lo que podría concluir. (¿Por qué hice este comentario? Porque no es realmente una respuesta ...)

Ryan Williams

T I M E (t) \subseteq A T I M E (t^{1 - ϵ})

$TIME(t) \subseteq ATIME(t^{1-\epsilon})$

P = R P

$P = RP$

T I M E (t) \subseteq S P A C E (t^{1 - ϵ})

$TIME(t) \subseteq SPACE(t^{1-\epsilon})$

ϵ > 0

$\epsilon > 0$

P = R P

$P = RP$

¿

Respuestas: