Apakah dengan fanout terikat lebih lemah dari ?

23

Dalam survei "Sirkuit Kuantum Kedalaman Kecil" oleh D. Bera, F. Green dan S. Homer (hlm. 36 dari ACM SIGACT News, Juni 2007, vol. 38, no. 2) , saya membaca kalimat berikut:

Versi klasik (di mana gerbang dan memiliki fanout paling konstan) terbukti lebih lemah dari .QAC0ANDORAC0

Referensi untuk klaim ini tidak ada. Saya akan memanggil kelas ini , di mana adalah singkatan dari "fanout terikat". (Kompleksitas Kebun Binatang sedang turun dan saya tidak dapat memverifikasi jika kelas tersebut sudah memiliki nama dalam literatur). Jika kita mengasumsikan fanout tanpa batas untuk bit input, maka rangkaian ini tampaknya setara dengan rumus kedalaman konstan hingga peningkatan polinomial dalam ukuran, sehingga klaim di atas tidak masuk akal. Sebaliknya, jika kita mengasumsikan fanout terbatas untuk bit input juga, maka saya tidak dapat memikirkan bahasa apa pun yang memisahkan kelas ini dari . Calon yang mungkin adalah bahasa , yaitu bahasa string dengan hanya satu 1. Mudah untuk ditampilkanACbf0bfAC0X:={x|weight(x)=1}XAC0 , tetapi saya tidak berhasil membuktikan bahwa .XACbf0

Pertanyaannya adalah:

Apakah sebenarnya lebih lemah dari ? Jika ya, ada ide atau referensi tentang cara membuktikannya? Dan apa bahasa yang memisahkan kedua kelas itu? Bagaimana dengan ? A C 0 XACbf0AC0X

Alessandro Cosentino
sumber
6
Bounding fan-out dari bit input akan membuat sirkuit berukuran linier. Setiap fungsi yang membutuhkan ukuran super-linear akan memisahkan mereka. SEBUAHC0
Kaveh
2
@Kaveh: Mungkin Anda bisa mengumumkan bahwa sebagai jawaban, dengan mungkin contoh fungsi eksplisit yang membutuhkan ukuran super-linear sirkuit dan mungkin referensi yang menunjukkan ukuran batas bawah? (Atau sertakan argumen dalam jawaban Anda jika itu sangat sederhana?)AC0
Robin Kothari
2
@ Kaveh Terima kasih. Aku tidak tahu bahwa pemisahan antara dan linier ukuran sirkuit konstan mendalam (rupanya disebut L C 0 ) dikenal. Referensi ini adalah "Pembatasan Deterministik dalam Kompleksitas Sirkuit" oleh S. Chaudhuri dan J. Radhakrishnan. @ Kaveh Bisakah Anda membuat komentar sebagai jawaban? SEBUAHC0L.C0
Alessandro Cosentino
2
Seperti yang dibahas pada pertanyaan lanjutan cstheory.stackexchange.com/questions/7447/… , sama dengan rumus ukuran linier. SEBUAHCbf0
domotorp

Jawaban:

23

Ikatan yang dipasang keluar dari bit input dan gerbang akan membuat ukuran rangkaian menjadi linier. Biarkan menjadi terikat pada kipas-keluar dari gerbang dan input. Ini adalah DAG dengan derajat keluar maksimum yang dibatasi oleh k dan panjang jalur maks . D. Jumlah kabel tersedia di setiap tingkat dapat meningkatkan k kali, dan jumlah kabel tersedia di atas adalah k n , sehingga jumlah total kabel di sirkuit yang paling k n Σ d i = 0 k ik d + 1 n yang merupakan O ( n ) .kkdkknknsaya=0dksayakd+1nHAI(n)

Setiap fungsi yang membutuhkan ukuran super-linear akan memisahkan kelas fungsi dengan dibatasi fan-out (diterapkan juga untuk masukan bit) dari A C 0 . Berikut ini beberapa contohnya:SEBUAHC0SEBUAHC0

  1. [CR96]: Fungsi yang membutuhkan ukuran super-linear adalah 1SEBUAHC0 -pilih pemilih14. A -approximate selector adalah fungsi yang nilainya:14

    • setiap kali jumlah 1 paling banyak n01 ,n4
    • setiap kali jumlah 0 s paling banyak n10 ,n4
    • dapat berupa atau 1 jika tidak.01
  2. [Ros08] menunjukkan bahwa -clique memiliki A C 0 fungsi kompleksitas n Θ ( k ) ( n 2 bit masukan yang mungkin tepi grafik dengan n simpul). Ini memberikan ukuran garis super rendah lowerbound untuk k > 2 .kSEBUAHC0nΘ(k)n2nk>2

  3. Mungkin saja untuk menggeneralisasi contoh dalam 2 dapat menjadi adanya substruktur nontrivial (memerlukan lebih dari satu bit) yang diinduksi dalam struktur yang tidak berurutan, misalnya:

    • keberadaan jalur panjang 2 dalam grafik yang diberikan,
    • ,#1(x)=2

    karena mereka membutuhkan jumlah gerbang super konstan tergantung pada bit yang tidak mungkin pada .SEBUAHCbf0

  4. Contoh termudah adalah gerbang duplikator, yaitu gerbang yang membuat salinan bit inputnya. Ini tidak mungkin di A C 0 b f karena hanya O ( 1 ) dari gerbang dapat bergantung pada setiap bit input.ω(1)SEBUAHCbf0HAI(1)

Juga setiap sirkuit ukuran S bisa berubah menjadi rumus ukuran paling k d S dan karena itu memiliki A C 0 b f rumus ukuran k 2 d + 1 n sehingga setiap fungsi superlinear A C 0 kompleksitas rumus tidak akan berada dalam A C 0 b f .SEBUAHCbf0SkdSSEBUAHCbf0k2d+1nSEBUAHC0SEBUAHCbf0


Referensi:

[CR96] S. Chaudhuri dan J. Radhakrishnan, " Pembatasan Deterministik dalam Kompleksitas Sirkuit ", 1996

[Ros08] Benjamin Rossman, " Pada Kerumitan Constant-Depth dari k-Clique ", 2008

[Juk] Stasys Jukna, " Kompleksitas Fungsi Boolean: Kemajuan dan Batas ", konsep

Kaveh
sumber
12
Pemisahan yang lebih baru antara dan A C 0 mengikuti dari hasil ini karena Benjamin Rossman. Dia menunjukkan bahwa untuk semua konstanta k (juga beberapa tumbuh k ) dan konstan d , setiap kedalaman d sirkuit untuk k -clique pada n grafik vertex harus memiliki ukuran Ω ( n k / 4 ) . Ini berarti bahwa hierarki bahasa diterima oleh A C 0 sirkuit ukuran n k (untuk berbagai kL.C0SEBUAHC0kkddknΩ(nk/4)AC0nkk) sebenarnya tak terbatas.
Srikanth
1
Saya memperbarui jawabannya, terima kasih kepada Alessandro, domotorp, Robin, Srikanth, dan Stasys.
Kaveh
1
@ Kaveh: Baiklah, terima kasih. Jika Anda menemukan cara untuk mengubah hasil Rossman, saya akan tertarik mendengarnya. Adapun fungsi ambang-2, saya pikir kita dapat menunjukkan itu tidak ada di kelas ini dengan mencatat bahwa semua fungsi di kelas ini memiliki rumus berukuran linier, dan ambang-2 memiliki ukuran rumus batas bawah . Ω(nlogn)
Robin Kothari
1
@Kaveh: Jika dengan , Anda berarti jalan panjang k , Anda harus diingat bahwa ada A C 0 sirkuit dari ukuran 2 k n O ( 1 ) untuk fungsi-fungsi ini (ini mengikuti dasarnya dari Warna teknik Coding dari Alon, Yuster, dan Zwick). Saya tidak yakin teknik Rossman memberikan batasan semacam ini (meskipun saya tidak tahu alasan mengapa tidak seharusnya). PkkAC02knO(1)
Srikanth
1
@ Kaveh: Maaf, saya seharusnya memberikan referensi. Makalah yang Anda tunjukkan memprakarsai metode pengkodean Warna untuk menemukan jalur dan subgraph lainnya dengan cepat. Amano, dalam makalah ini , adalah yang pertama menunjukkan bahwa algoritma dapat diimplementasikan dalam . AC0
Srikanth