Apa kelas terbesar dari fungsi

Dalam [1] dinyatakan bahwa

"Ini masih menjadi pertanyaan terbuka apakah setiap fungsi di memiliki sirkuit (meskipun setidaknya diketahui bahwa tidak semua fungsi memiliki sirkuit DLogTime-uniform-uniform )." $\#P$ $TC^0$ $\#P$ $TC^0$

sirkuit yang dihasilkan oleh fungsi DLogTime tidak mengandung . Kami tidak tahu apakah sirkuit yang dihasilkan oleh fungsi sewenang-wenang tidak mengandung . $TC^0$ $\#P$ $TC^0$ $\#P$

Adakah yang diketahui tentang kasus-kasus di antara keduanya? Misalnya apakah diketahui apakah sirkuit yang dihasilkan oleh tidak mengandung ? $TC^0$ $L$ $\#P$

[1] Agarwal, Allender, dan Datta, "Pada , , dan Sirkuit Aritmatika" $TC^0$ $AC^0$

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

@ Kaveh Anda dapat menyimpan jawaban Anda. Mungkin Anda bisa mengatakan itu untuk versi yang salah.

T ....

Saya tidak berpikir itu menjawab pertanyaan, jadi itu bukan jawaban. :)

Kaveh

Yah itu punya beberapa detail yang bagus.

T ....

Jawaban:

Ini adalah masalah terbuka (menarik), sejauh yang saya tahu. Rahul Santhanam dan saya secara eksplisit menyebutkan masalah membuktikan Permanen tidak dalam LOGSPACE-uniform TC0 dalam makalah CCC'13 kami (Tentang Keseragaman Sedang dan Sirkuit Bawah Batas).

Ryan Williams
sumber

Lebih konservatif, orang bisa bertanya tentang 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}$ -keseragaman.

$\;\;\:\:$

@Ricky Demer, itu sudah diketahui. Lihat misalnya Chen dan Kabanets eccc.hpi-web.de/report/2012/007/download

Ryan Williams

Nah, dari makalah itu, POLYLOGTIME adalah "kelas fungsi C sehingga kita tahu #P tidak terkandung dalam" C-uniform TC0.

$\:$ Selanjutnya, dengan padding, POLYLOGTIME lebih besar dari DLOGTIME.

Tepat ... Jadi, batas bawah untuk keseragaman yang Anda sebutkan di atas sudah diketahui.

Ryan Williams

... dan, batas bawah itu tidak disebutkan dalam jawaban Anda.

$\;$