Keacakan dan kelas kompleksitas sirkuit kecil

Biarkan menjadi kelas kompleksitas dan menjadi mitra acak dari didefinisikan sebagai sehubungan dengan . Lebih formal kami menyediakan banyak bit acak polinomi dan kami menerima input jika probabilitas untuk menerima lebih dari . $\mathcal{C}$ $\textrm{BP-}\mathcal{C}$ $\mathcal{C}$ $\textrm{BPP}$ $\textrm{P}$ $\frac{2}{3}$

Diketahui bahwa untuk kelas sirkuit tidak seragam kita memiliki $\textrm{BPAC}^0=\textrm{AC}^0$ :

Miklós Ajtai, Michael Ben-Or: A Theorem on Probabilistic Constant Depth Computing STOC 1984: 471-474

Apakah generalisasi teorema ini diketahui? Misalnya, apakah kita tahu jika $\mathrm{BPNC}^1=\mathrm{NC}^1$ (masih dalam pengaturan yang tidak seragam)? Pertanyaan terakhir ini tampaknya tidak sepele bagi saya karena tampaknya masuk akal bahwa misalnya $s,t\textrm{-Connectivity}$ ada di $\textrm{BPNC}^1$ .

Posting yang relevan tentang masalah ini: /mathpro/35184/use-of-randomness-in-constant-parallel-time

circuit-complexity randomized-algorithms CP
sumber

Apa yang mendorong firasat Anda tentang konektivitas?

Michaël Cadilhac

Apakah Anda bertanya tentang kelas sirkuit yang seragam ? Sudah cukup jelas bahwa kelas tidak seragam seperti ditutup di bawah operator BP.

N C^{1}

$\mathrm{NC^1}$

Emil Jeřábek

Cukup gunakan argumen yang sama seperti untuk P / poly. Anda hanya perlu fungsi mayoritas, yang dapat didefinisikan dalam . (Ajtai dan Ben-Atau perlu lebih banyak pekerjaan karena mayoritas tidak tersedia di .)

T C^{0} \subseteq N C^{1}

$\mathrm{TC^0\subseteq NC^1}$

A C^{0}

$\mathrm{AC^0}$

Emil Jeřábek

@ EmilJeřábek kamu benar sekali. Untuk setiap kelas rangkaian non-unifom di atas kita memiliki . Terima kasih banyak.

{TC}^{0}

$\textrm{TC}^0$

BP - C = C

$\textrm{BP}-\mathcal{C}=\mathcal{C}$

@ EmilJeřábek: Ah, begitu. Saya pikir itu batas; itu jelas bukan pertanyaan penelitian , tetapi jelas ditanyakan dengan sungguh-sungguh oleh seseorang dengan pengalaman penelitian dalam kompleksitas, yang hanya disesatkan dengan mencoba memperluas Ajtai-Ben-Atau daripada menggunakan pendekatan yang lebih mudah.

Joshua Grochow

Sebagian besar kelas kompleksitas tidak seragam— termasuk — ditutup di bawah operator dengan argumen yang sama dengan : menggunakan batas Chernoff-Hoeffding, probabilitas dari kesalahan dapat dikurangi di bawah dengan menjalankan instance sirkuit dengan bit acak independen secara paralel, dan mengambil suara terbanyak; kemudian oleh ikatan terikat, urutan bit acak memberikan hasil yang benar untuk semua input panjang secara bersamaan dengan probabilitas nol, dan khususnya, ada urutan seperti itu. Kita bisa memasukkannya ke sirkuit. $\mathrm{NC^1}$ $\mathrm{BP}$ $\mathrm{BPP\subseteq P/poly}$ $2^{-n}$ $O(n)$ $2^n$ $n$

Argumen ini berlaku untuk setiap kelas sirkuit yang ditutup dengan mengambil sebagian besar salinan paralel sirkuit, dan memperbaiki gerbang input ke konstanta. Dalam praktiknya, ini berarti setiap kelas non-seragam yang layak di atas , karena mayoritas dapat dihitung dalam . $O(n)$ $\mathrm{TC^0}$ $\mathrm{TC^0}$

Buktinya lebih rumit untuk , karena kelas ini tidak menghitung fungsi mayoritas. (Meskipun saya belum melihat kertas Ajtai dan Ben-Or, saya kira mereka menggunakan semacam perkiraan mayoritas.) $\mathrm{AC^0}$

Emil Jeřábek
sumber

Keacakan dan kelas kompleksitas sirkuit kecil

Jawaban: