O que é a maior classe de funções

8

Em [1] afirma-se que

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

circuitos gerados por funções dlogtime não contém # P . Não sabemos se T C 0 circuitos gerados por funções arbitrárias não contém # P .TC0#PTC0#P

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

  • [1] Agarwal, Allender e Datta, "Em , A C 0 e circuitos aritméticos"TC0AC0
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
1
Bem, tinha alguns detalhes legais.
T ....

Respostas:

6

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
1
Mais conservadoramente, pode-se perguntar sobre o DTISP (log(n)(log(log(n)))o(1),O(log(n)))-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.