¿Cuál es la clase más grande de funciones tal manera que sepamos que no está contenido en generado por ?

En [1] se afirma que

"Sigue siendo una pregunta abierta si cada función en tiene circuitos (aunque al menos se sabe que no todas las funciones tienen circuitos uniformes DLogTime )". $\#P$ $TC^0$ $\#P$ $TC^0$

$TC^0$ circuitos generados por las funciones DLogTime no contienen . No sabemos si los circuitos generados por funciones arbitrarias no contienen . $\#P$ $TC^0$ $\#P$

¿Hay algo conocido sobre los casos entre estos dos? Por ejemplo, ¿se sabe si los circuitos generados por no contienen ? $TC^0$ $L$ $\#P$

[1] Agarwal, Allender y Datta, "En , y circuitos aritméticos" $TC^0$ $AC^0$

cc.complexity-theory complexity-classes circuit-complexity counting-complexity permanent T ....
fuente

@Kaveh Puedes conservar tu respuesta. Tal vez puedas comentar que fue para una versión errónea.

T ....

No creo que responda la pregunta, por lo que no es realmente una respuesta. :)

Kaveh

Bueno, tenía algunos detalles agradables.

T ....

Respuestas:

Este es un problema abierto (interesante), que yo sepa. Rahul Santhanam y yo mencionamos explícitamente el problema de probar que Permanente no está en LOGSPACE-uniform TC0 en nuestro artículo CCC'13 (Sobre uniformidad media y límites inferiores del circuito).

Ryan Williams
fuente

De manera más conservadora, uno podría preguntar sobre DTISP -uniformidad.

(\log (n) \cdot (\log (\log (n)))^{o (1)}, O (\log (n)))

$\hspace{-0.04 in}\left(\log(n)\hspace{-0.04 in}\cdot \hspace{-0.03 in}(\log(\log(n)))^{o(1)}\hspace{-0.02 in},\hspace{-0.02 in}O(\log(n))\right)\hspace{-0.02 in}$

$\;\;\:\:$

@Ricky Demer, eso ya se sabe. Véase, por ejemplo, Chen y Kabanets eccc.hpi-web.de/report/2012/007/download

Ryan Williams

Bueno, según ese documento, POLYLOGTIME es una "clase de funciones C tal que sabemos que #P no está contenido en" C0 uniforme TC0. Además, al rellenar, POLYLOGTIME es más grande que DLOGTIME.

$\:$

Exactamente ... Entonces, ya se conocen límites inferiores para la uniformidad que mencionó anteriormente.

Ryan Williams

... y esos límites inferiores no se mencionan en su respuesta.

$\;$