Protokol nomor partisi dan kompleksitas komunikasi deterministik

Selain kompleksitas komunikasi (deterministik) dari suatu relasi , ukuran dasar lain untuk jumlah komunikasi yang dibutuhkan adalah nomor partisi protokol . Hubungan antara kedua ukuran ini diketahui hingga faktor konstan. Monograf oleh Kushilevitz dan Nisan (1997) memberikan$cc(R)$$R$ $pp(R)$

Mengenai ketimpangan kedua, mudah untuk memberikan (keluarga tak terbatas) hubungan denganlog 2 ( p p ( R ) ) = c c ( R $R$$\log_2(pp(R)) = cc(R)$ .

Mengenai ketimpangan pertama, Doerr (1999) menunjukkan bahwa kita dapat mengganti faktor pada ikatan pertama denganc = $c=3$$c=2.223$ . Dengan berapa banyak ikatan pertama dapat ditingkatkan, jika sama sekali?

Motivasi tambahan dari kompleksitas deskriptif: Meningkatkan konstanta akan menghasilkan batas bawah yang ditingkatkan pada ukuran minimum ekspresi reguler yang setara dengan DFA yang diberikan yang menggambarkan beberapa bahasa yang terbatas, lihat Gruber dan Johannsen (2008). $2.223$

Meskipun tidak terkait langsung dengan pertanyaan ini, Kushilevitz, Linial dan Ostrovsky (1999) memberi hubungan dengan , di mana adalah yang nomor partisi persegi panjang .c c ( R ) / ( 2 - o ( 1 ) ) ≥ log 2 ( r p ( R ) ) r p ( R $R$$cc(R)/(2-o(1)) \ge \log_2(rp(R))$$rp(R)$

EDIT: Perhatikan bahwa pertanyaan di atas setara dengan pertanyaan berikut dalam kompleksitas sirkuit Boolean: Berapakah konstanta optimum sehingga setiap rumus DeMorgan boolean dari leafsize L dapat ditransformasikan menjadi formula kedalaman yang setara di sebagian besar ?c log 2$c$$c \log_2L$

Referensi :

• Kushilevitz, Eyal; Nisan, Noam: Kompleksitas Komunikasi. Cambridge University Press, 1997.
• Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: Dugaan Linear-Array dalam Kompleksitas Komunikasi Adalah Salah, Combinatorica 19 (2): 241-254, 1999.
• Doerr, Benjamin: Kompleksitas Komunikasi dan Nomor Partisi Protokol, Laporan Teknis 99-28, Berichtsreihe des Mathematischen Seminarars der Universität Kiel, 1999.
• Gruber, Hermann; Johannsen, Jan: Batas Bawah Optimal pada Ukuran Ekspresi Reguler menggunakan Kompleksitas Komunikasi. Dalam: Yayasan Sains Perangkat Lunak dan Struktur Komputasi 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Peloncat.

Ok, jadi izinkan saya mencoba untuk membuktikan bahwa dua sudah cukup, yaitu . Maaf tapi kadang-kadang saya menulis daun bukannya jumlah daun / pp (R), setiap kali jumlahnya lebih kecil dari 1, saya jelas-jelas maksudkan ini. Juga, saya biasanya menulis <bukan$cc(R)\le 2\log_2(pp(R))$$\le$ untuk meningkatkan keterbacaan non-tex.

Secara tidak langsung anggap ada R yang tidak benar dan mari kita ambil R dengan pp sekecil mungkin (R) yang melanggar ketimpangan. Kami pada dasarnya harus menunjukkan bahwa dengan menggunakan dua bit, kami dapat membagi dua jumlah daun di keempat hasil dari pohon protokol, kemudian kami selesai menggunakan induksi.

Nyatakan set input Alice yang mungkin oleh X dan Bob oleh Y. Ambil pusat pohon protokol yang mencapai daun pp (R), yaitu node yang menghapus pohon yang jatuh menjadi tiga bagian, masing-masing memiliki paling banyak 1/2 dari pp (R) pergi, dan menunjukkan input yang sesuai dengan X0 dan Y0. Tanpa kehilangan sifat umum kita dapat menduga bahwa Alice berbicara di pusat dan dia mengatakan apakah inputnya milik XL atau XR, yang penyatuan terputus-putusnya adalah X0. Sebutkan rasio daun terhadap pp (R) dalam XL Y0 oleh L, dalam XR × Y0 oleh R dan sisanya oleh D. Sekarang kita membagi sisanya menjadi tiga bagian lagi, mirip dengan Doerr, menunjukkan daun yang persegi panjangnya memotong Y0 × X oleh A, yang persegi panjangnya memotong X0 $\times$$\times$$\times$$\times$ Y oleh B dan sisanya oleh C. Perhatikan bahwa A + B + C = D.

Sekarang kita tahu bahwa L + R> 1/2, L, R <1/2 dan tanpa kehilangan generalitas kita dapat menganggap bahwa L adalah paling banyak R. Kita juga tahu D = A + B + C <1/2. Oleh karena itu 2L + A + B <1, dari mana kita tahu bahwa L + A <1/2 atau L + B <1/2, ini akan menjadi dua kasus kami.

Kasus L + A <1/2: Bob pertama memberi tahu apakah inputnya milik Y0 atau tidak. Jika tidak, kami memiliki paling banyak D <1/2 daun tersisa. Jika ya, maka Alice memberi tahu apakah inputnya milik XR atau tidak. Jika tidak, kami memiliki paling banyak L + A <1/2 daun tersisa. Jika ya, maka kita memiliki R <1/2 daun tersisa.

Kasus L + B <1/2: Pertama Alice memberi tahu apakah inputnya milik XR atau tidak. Jika ya, maka Bob mengatakan apakah miliknya Y0 atau tidak, tergantung pada ini kita memiliki R atau B yang tersisa. Jika input Alice tidak di XR, maka Alice mengatakan apakah inputnya ada di XL atau tidak. Jika ya, maka kita memiliki L + B <1/2 daun yang tersisa. Jika tidak, kami memiliki paling banyak D <1/2 daun tersisa.

Dalam semua kasus kita selesai. Biarkan aku tahu apa yang Anda pikirkan.

$c\le 2$$c \le 1.73$

Referensi

Stasys Jukna. Kompleksitas Fungsi Boolean: Kemajuan dan Batas. Springer, 2012.

VM Khrapchenko. Pada hubungan antara kompleksitas dan kedalaman. Metody Diskretnogo Analiza dalam Synthezis of Control Systems 32: 76-94, 1978.