O que é a maior classe de funções

Em [1] afirma-se que

"Continua sendo uma questão em aberto se todas as funções em possuem circuitos (embora seja pelo menos sabido que nem todas as funções possuem circuitos uniformes para DLogTime )." $\#P$ $TC^0$ $\#P$ $TC^0$

circuitos gerados por funções dlogtime não contém . Não sabemos se circuitos gerados por funções arbitrárias não contém . $TC^0$ $\#P$ $TC^0$ $\#P$

Existe algo conhecido sobre os casos entre esses dois? Por exemplo, sabe-se se circuitos gerados por não contêm ? $TC^0$ $L$ $\#P$

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

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

@ Kaveh Você pode manter sua resposta. Talvez você possa observar que foi para uma versão incorreta.

T ....

Eu não acho que responda à pergunta, então não é realmente uma resposta. :)

Kaveh

Bem, tinha alguns detalhes legais.

T ....

Respostas:

Este é um problema aberto (interessante), até onde eu sei. Rahul Santhanam e eu mencionamos explicitamente o problema de provar que o Permanent não está no TC0 uniforme do LOGSPACE em nosso artigo do CCC'13 (Sobre limites médios de uniformidade e circuito inferior).

Ryan Williams
fonte

Mais conservadoramente, pode-se perguntar sobre o DTISP

(\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}$ -uniformidade.

$\;\;\:\:$

@ Ricky Demer, isso já é conhecido. Veja, por exemplo, Chen e Kabanets eccc.hpi-web.de/report/2012/007/download

Ryan Williams

Bem, nesse documento, POLYLOGTIME é uma "classe de funções C, de modo que sabemos que #P não está contido em" TC0 uniforme C.

$\:$ Além disso, por preenchimento, POLYLOGTIME é maior que DLOGTIME.

Exatamente ... Então, limites mais baixos para a uniformidade que você mencionou acima já são conhecidos.

Ryan Williams

... e esses limites inferiores não são mencionados na sua resposta.

$\;$