Apakah

21

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 ) )?2HAI(nϵ)ϵ<1d=HAI(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 / ϵ ) ).NC12HAI(nϵ)d0<ϵddHAI(1/ϵ)

Pertanyaannya adalah:

apakah ada alasan yang membuat keberadaan sirkuit seperti itu untuk sirkuit ukuran polinomial umum tidak mungkin?

Kaveh
sumber
3
Jika dengan ukuran subeksponensial yang Anda maksud adalah (bukan 2 o ( n ) ) dan dengan kedalaman terikat Anda berarti kedalaman konstan, maka paritas tidak memiliki sirkuit kedalaman terikat ukuran subeksponensial tanpa asumsi. 2nHai(1)2Hai(n)
MCH
Anda harus memposting komentar Anda sebagai jawaban. Anda akan mendapatkan kredit untuk itu, dan jika sesuai dapat ditandai sebagai jawaban yang diterima. Ini juga akan mencegah pertanyaan agar tidak secara otomatis dikirim ulang secara berkala oleh bot Komunitas.
Suresh Venkat
@MCH, saya memperbarui pertanyaan untuk memperjelas apa yang saya maksud dengan ukuran subexponential.
Kaveh
3
Dalam kasus seragam, Anda dapat mengatakan sesuatu ( menyiratkan batas waktu yang lebih rendah untuk SAT). Tetapi dalam kasus non-seragam, kami tahu tidak ada batas bawah yang kuat untuk P / poli, dan tidak ada batas bawah yang kuat untuk definisi Anda tentang sirkuit kedalaman-konstan ukuran sub-eksponensial. Misalnya masih mungkin E X P N PTsayaM.E(t)ΣHAI(d)TsayaM.E[n1/d]EXPNPdapat disimulasikan di salah satu dari kelas-kelas ini. Jadi saya tidak yakin apa yang bisa Anda simpulkan. (Mengapa saya membuat komentar ini? Karena itu bukan jawaban ...)
Ryan Williams
2
Ya, dianggap tidak mungkin. Sipser (CCC '86) menunjukkan bahwa P = R P atau T I M E ( t ) S P A C E ( t 1 - ϵ ) untuk beberapa ϵ > 0TsayaM.E(t)SEBUAHTsayaM.E(t1-ϵ)P=RPTsayaM.E(t)SPSEBUAHCE(t1-ϵ)ϵ>0 , berdasarkan hipotesis konstruksi ekspander tertentu yang kemudian terbukti benar oleh Saks, Srinivasan, dan Zhou. Ini diambil sebagai bukti bahwa . Kemudian bekerja pada kekerasan vs keacakan membuat koneksi lebih tepat. P=RP
Ryan Williams

Jawaban:

8

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

V Vinay
sumber
Terima kasih atas petunjuk yang menarik. Saya terutama tertarik pada kemungkinan adanya simulasi seperti itu (yaitu dugaan dan hipotesis yang akan menyiratkan jawaban negatif atau positif untuk dan kelas serupa seperti N C di mana jawabannya tidak diketahui tanpa syarat.) Apakah kita tahu hal seperti itu? P/halHailyNC
Kaveh
Sayangnya, tidak ada apa-apa. Saya sedang memikirkan beberapa surat kabar lama oleh Buhrman / Homer dan yang lainnya tetapi tidak mengingat hal semacam itu. Akan kembali jika sesuatu muncul.
V Vinay