Apakah ada hipotesis kompleksitas / kripto yang masuk akal yang mengesampingkan kemungkinan bahwa sirkuit ukuran polinomial memiliki ukuran subeksponensial (yaitu dengan ϵ < 1 ) sirkuit batas-kedalaman ( d = O ( 1 ) )?
Kita tahu bahwa setiap fungsi yang dihitung oleh sirkuit dapat dihitung dengan sirkuit kedalaman d ukuran 2 O ( n ϵ ) (menggunakan AND, OR, dan NOT gerbang, fan-in tanpa batas) (untuk setiap 0 < ϵ ada a d dan d dapat dianggap sebagai O ( 1 / ϵ ) ).
Pertanyaannya adalah:
apakah ada alasan yang membuat keberadaan sirkuit seperti itu untuk sirkuit ukuran polinomial umum tidak mungkin?
Jawaban:
Apa yang Anda minta harus memiliki konsekuensi buruk tetapi saya tidak dapat segera memikirkannya. Jadi saya hanya punya beberapa petunjuk tentang apa yang kita ketahui.
Lihat Viola's Pada kekuatan perhitungan kedalaman kecil Yang terbaik yang kita tahu adalah konstruksi Valiant untuk sirkuit boolean: sirkuit ukuran log kedalaman linier untuk kedalaman 3 sirkuit subexp. (Kami lebih tahu untuk sirkuit aritmatika .) Ada juga beberapa hasil Beigel / Tarui pada ACC yang mulai terkandung dalam sirkuit kedalaman terbatas ukuran superpoly. Saya tidak ingat itu diperluas ke semua .NC1
sumber