Was ist die größte Klasse von Funktionen

In [1] heißt es:

„Es bleibt eine offene Frage, ob jede Funktion in hat Schaltungen (obwohl es ist zumindest bekannt , dass nicht alle Funktionen haben DLogTime förmige Schaltungen).“ $\#P$ $TC^0$ $\#P$ $TC^0$

Schaltungen erzeugt durch DLogTime Funktionen nicht enthält . Wir wissen nicht, ob -Schaltungen, die durch beliebige Funktionen erzeugt werden, kein enthalten. $TC^0$ $\#P$ $TC^0$ $\#P$

Ist etwas über die Fälle zwischen diesen beiden bekannt? Ist beispielsweise bekannt, ob von erzeugte -Schaltungen nicht enthalten ? $TC^0$ $L$ $\#P$

[1] Agarwal, Allender und Datta, "On , und Arithmetic Circuits". $TC^0$ $AC^0$

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

@ Kaveh Sie können Ihre Antwort behalten. Vielleicht können Sie bemerken, dass es sich um eine fehlerhafte Version handelte.

T ....

Ich denke nicht, dass es die Frage beantwortet, also ist es nicht wirklich eine Antwort. :)

Kaveh

Nun, es hatte einige nette Details.

T ....

Antworten:

Dies ist meines Wissens ein (interessantes) offenes Problem. Rahul Santhanam und ich erwähnen ausdrücklich das Problem, zu beweisen, dass Permanent nicht in LOGSPACE-Uniform TC0 enthalten ist, in unserem CCC'13-Artikel (On Medium-Uniformity and Circuit Lower Bounds).

Ryan Williams
quelle

Konservativer könnte man nach DTISP fragen

(\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}$ -Gleichmäßigkeit.

$\;\;\:\:$

@ Ricky Demer, das ist schon bekannt. Siehe zum Beispiel Chen und Kabanets eccc.hpi-web.de/report/2012/007/download

Ryan Williams

Nun, in diesem Artikel ist POLYLOGTIME eine "Klasse von Funktionen C, so dass wir wissen, dass #P nicht in" C-Uniform TC0 enthalten ist.

$\:$ Darüber hinaus ist POLYLOGTIME durch Auffüllen größer als DLOGTIME.

Genau ... Die unteren Grenzen für die oben erwähnte Einheitlichkeit sind also bereits bekannt.

Ryan Williams

... und diese unteren Grenzen werden in Ihrer Antwort nicht erwähnt.

$\;$