Batas bawah untuk rumus kedalaman konstan?

21

Kita tahu banyak tentang batasan-batasan (kedalaman polinomial) sirkuit-konstan. Karena (kedalaman polinomial) rumus kedalaman konstan adalah model perhitungan yang bahkan lebih terbatas, semua masalah yang diketahui tidak ada dalam AC ⁰ juga tidak dapat dihitung dengan rumus kedalaman konstan. Namun, karena ini model yang lebih mudah, saya menduga ada lebih banyak masalah yang diketahui tidak dapat dihitung dalam model ini. Apakah ini sudah dipelajari? (Saya menduga sudah, tapi saya mungkin tidak menggunakan istilah pencarian yang tepat.)

Secara khusus saya tertarik pada pertanyaan berikut: Apakah ada beberapa fungsi f, yang dapat dihitung oleh sirkuit AC ⁰ ukuran S, tetapi membutuhkan rumus ukuran kedalaman-konstan paling tidak kuadratik dalam S, atau super polinomial dalam S? Apa hasil yang paling dikenal dari jenis ini?

Dalam hal tidak jelas apa yang saya maksud dengan rumus kedalaman konstan, maksud saya rumus yang jika Anda tulis sebagai pohon (dengan gerbang internal menjadi AND / ATAU / TIDAK gerbang, dan meninggalkan input), maka pohon ini memiliki konstanta tinggi. Setara, rumus kedalaman konstan adalah sirkuit kedalaman konstan di mana semua gerbang non-input memiliki fanout 1.

cc.complexity-theory circuit-complexity lower-bounds Robin Kothari
sumber

11

Sangat mudah untuk mengubah sirkuit kedalaman konstan ke formula kedalaman konstan dengan kedalaman yang sama dengan peningkatan ukuran polinomial, dengan membuat salinan gerbang yang digunakan lebih dari sekali. Jika kedalaman rangkaian adalah dan ukurannya adalah , rumus akan memiliki kedalaman dan ukuran . Karena itu jawabannya adalah tidak. $d$ $O(p(n))$ $d$ $O((p(n))^d)$

Kaveh
sumber

5

ini memberikan lebih dari peningkatan kuadrat dalam ukuran. (Padahal, bukan peningkatan super-polinomial, tentu saja.)

Iddo Tzameret

2

Terima kasih atas jawabannya. Adakah gagasan tentang fungsi tertentu f yang memiliki rangkaian ukuran S yang konstan, tetapi membutuhkan rumus ukuran S ^ 2, atau S ^ 10, dll?

Robin Kothari

3

Saya pikir hubungan antara kedalaman dan ukuran rangkaian masih terbuka (Diketahui bahwa "kedalaman" adalah teta dari ukuran formula). Lihat bab 7 dan 8 dalam buku Wegener "Kompleksitas fungsi boolean" untuk beberapa fungsi dengan ukuran rumus eksplisit batas bawah. Ada satu dengan hampir peningkatan kuadrat (

), tidak pemberitahuan sesuatu yang lebih baik.

n^{2} / l o g n

$n^2/log n$

Kaveh

17

Pertanyaan ini telah sepenuhnya diselesaikan (hingga faktor konstan) oleh hasil terbaru dari Benjamin Rossman ( http://eccc.hpi-web.de/report/2013/169/ ).

Seperti yang ditunjukkan Kaveh di atas, sirkuit kedalaman , ukuran , dapat dikonversi ke rumus kedalaman , ukuran . $d$ $S$ $d$ $S^d$

Rossman menunjukkan bahwa ini pada dasarnya ketat. Untuk setiap kedalaman , ia menunjukkan fungsi yang dapat dihitung oleh sirkuit kedalaman-kedalaman konstan dan ukuran , tetapi rumus kedalaman-konstan apa pun (atau bahkan $d$ $d$ $S = O(n^3)$ -depth formula) membutuhkan ukuran untuk menghitungnya. $\sqrt{\log n}$ $S^{\Omega(d)}$

(Lupa mengatakan ini sebelumnya: Terima kasih kepada Benjamin Rossman karena memberi tahu saya tentang hasil ini.)

Robin Kothari
sumber

Batas bawah untuk rumus kedalaman konstan?

Jawaban: