Apakah

$\mathsf{TC^0}$ $\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ $d$

Entri Kebun Binatang untuk $\mathsf{TC^0}$ hanya menyebutkan pemisahan antara kedalaman 2 dan 3.

Juga adakah referensi standar untuk fakta bahwa $\mathsf{AC^0_d}$ hierarki tidak runtuh?

cc.complexity-theory reference-request complexity-classes circuit-complexity bounded-depth Kaveh
sumber

Pertanyaan terkait adalah, berapa banyak fungsi berbeda yang ada di

A C_{d}^{0}

$AC_d^0$ /

T C_{d}^{0}

$TC_d^0$ ? Batas bawah yang wajar pada jumlah ini akan menjawab pertanyaan Anda. Juga bukti keketatan untuk lemma beralih Hastad mungkin akan menjawab pertanyaan kedua Anda.

MCH

Untuk pertanyaan kedua, saya percaya ini pertama kali dibuktikan dalam kertas STOC '83 milik Sipser "Borel set dan kompleksitas sirkuit" . Ini hanya memberikan batas bawah super-polinomial. Batas bawah eksponensial pertama diberikan oleh Yao, kemudian ditingkatkan oleh Håstad.

Robin Kothari

@MCH, maksud Anda menulis

T C_{d}^{0} / A C_{d}^{0}

$\mathsf{TC^0_d}/\mathsf{AC^0_d}$ ? Atau maksud Anda jumlah kelas ekivalensi masalah dalam

T C_{d}^{0}

$\mathsf{TC^0_d}$ wrt

A C_{d}^{0}

$\mathsf{AC^0_d}$ ?

Kaveh

Apa yang saya maksud adalah sangat sederhana: Berapa banyak fungsi berbeda yang dapat oleh kelas dari ukuran ? (Kita dapat memperkirakan jumlah sirkuit dengan sangat mudah tetapi kita harus berhati-hati bahwa beberapa dari mereka dapat menghitung fungsi yang sama.) Setelah Anda menunjukkan bahwa jumlah ini bertambah dengan , Anda selesai.

A C_{d}^{0}

$AC_d^0$

s

$s$

d

$d$

MCH

@Dilworth, tidak seragam. Menghitung tampaknya tidak berhasil, jika tidak, seperti yang saya catat di bawah ini, kita dapat memisahkan dari yang terbuka.

T C^{0}

$\mathsf{TC^0}$

N C^{1}

$\mathsf{NC^1}$

Kaveh

Jawaban:

Kami tahu tidak ada batas bawah yang baik (artinya, katakanlah, batas bawah superpolynomial untuk bahasa di ) untuk sirkuit ambang batas kedalaman 2 (bobot tidak terikat). Kedalaman 3 sirkuit dibangun dari gerbang mayoritas, yaitu berisi kelas ini, dan dengan demikian kita juga tidak mengenal batas bawah yang baik untuk kelas ini. $\mathsf{NEXP}$ $\mathsf{TC}^0_3$

Kristoffer Arnsfelt Hansen
sumber

Ini menjawab pertanyaan saya. Terima kasih Kristoffer.

Kaveh

Seperti yang saya tulis di komentar di atas, bahkan jika masalah di NEXP tidak diketahui berada di luar TC , bukankah masih mungkin bahwa hierarki TC yang tidak seragam layak melalui argumen penghitungan yang terikat lebih rendah?

_{2}^{0}

$^0_2$

^{0}

$^0$

Dilworth

Juga, bolehkah saya bertanya, bagaimana ini konsisten dengan batas bawah eksponensial yang diketahui pada TC dan pemisahan kedalaman 3 dari sirkuit ambang batas kedalaman 2, seperti yang dilaporkan dalam kebun binatang kompleksitas? Apakah saya melewatkan sesuatu?

_{2}^{0}

$_2^0$

Dilworth

@ Dworthworth, saya pikir itu karena itu didefinisikan menggunakan Mayoritas bukan Ambang.

Kaveh

Hmm .. apa maksudmu tepatnya? Apakah ini terkait dengan catatan yang dibuat oleh Kristoffer tentang "bobot yang tidak terikat"?

Dilworth

Jika saya tidak melakukan kesalahan, sepertinya membuktikan bahwa tidak runtuh setidaknya sama sulitnya dengan memisahkan dari : $\mathsf{TC^0_d}$ $\mathsf{NC^1}$ $\mathsf{TC^0}$

Mari kita tunjukkan masalah Evaluasi Formula Boolean oleh . selesai untuk bawah . $BFE$ $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0}$

Oleh Manindra Agrawal, Eric Allender, dan Steven Rudich, " Pengurangan dalam Kompleksitas Sirkuit: Teorema Isomorfisme dan Teorema Gap ", 1999, lengkap untuk bawah . $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0_2}$

Asumsikan . Kemudian untuk beberapa . Karena itu . Yang berarti . $\mathsf{NC^1}=\mathsf{TC^0}$ $BFE \in \mathsf{TC^0_d}$ $d$ $\mathsf{NC^1} \subseteq \mathsf{TC^0_{d+2}}$ $\mathsf{TC^0} \subseteq \mathsf{TC^0_{d+2}}$

Jadi untuk semua kita memiliki $d$

$\mathsf{TC^0} \not\subseteq \mathsf{TC^0_d}$ menyiratkan dan . $\mathsf{NC^1} \not\subseteq \mathsf{TC^0_{d+2}}$ $BFE \notin \mathsf{TC^0_d}$

Kaveh
sumber