Kompleksitas komunikasi dengan wasit

Asumsikan kerangka kerja dalam kompleksitas komunikasi di mana kita memiliki dua pemain A (kutu) dan B (ob) dan R (eferee). A dan B tidak berkomunikasi secara langsung satu sama lain. Dalam setiap putaran komunikasi, masing-masing dari mereka mengirim pesan ( , ) ke R. R menghitung dua fungsi dan dan mengirimkan hasilnya kepada mereka. Fungsinya diperbaiki. Idenya adalah bahwa komunikasi antara para pemain dibatasi. Selain itu, wasit mungkin melakukan beberapa pemrosesan pesan. $m_A$ $m_B$ $f_A(m_A,m_B)$ $f_B(m_A,m_B)$

Contoh:

A dan B mengirim dua nomor (besar yang sewenang-wenang) ke R, R memeriksa yang mana yang lebih besar dan memberi tahu para pemain.

Dalam kerangka kerja ini, kita dapat merancang protokol sederhana yang dengan mudah menghitung fungsi berikut menggunakan satu putaran. A dan B mengirim dan ke R, R mengembalikan jawabannya kepada mereka, dan mereka mengeluarkan jawabannya. $x$ $y$

f (x, y) = {\begin{cases} 0 & x \leq y \\ 1 & o w \end{cases}

$f(x,y)= \begin{cases}0 & x\leq y\\ 1 & ow \end{cases}$

Jelas ini bukan kasus yang menarik, karena fungsi yang kita hitung sama dengan fungsi wasit. Kasus yang lebih menarik adalah ketika kita memiliki ketidaksetaraan linear tetap dan nilai-nilai untuk variabel dipartisi antar pemain (A memiliki dan B memiliki ). Tugasnya adalah memutuskan apakah ketidaksetaraan itu benar. Protokol dalam hal ini adalah bahwa pemain menghitung bagian mereka dan kemudian mengirimnya ke wasit. $\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$ $\vec{x}$ $\vec{y}$

Pertanyaan:

Apakah kompleksitas komunikasi semacam ini telah dipelajari? Jika ya, di mana saya dapat menemukan lebih banyak tentang ini?

Catatan 1: pada halaman 49 Kushilevitz dan Nisan menyebutkan kerangka kerja yang melibatkan wasit tetapi tampaknya sangat berbeda dari apa yang saya tanyakan.

Catatan 2: Saya tidak yakin jika memanggil R wasit adalah hal yang benar, silakan berkomentar jika Anda memiliki saran yang lebih baik.

cc.complexity-theory reference-request communication-complexity Kaveh
sumber

model yang Anda sebutkan disebut "Simultanous Message Passing"

Marcos Villagra

periksa makalah ini ( arxiv.org/abs/quant-ph/0102001 ) dan rujukannya. Secara khusus, periksa kertas oleh Ambainis, dan Newman dan Szegedy.

Marcos Villagra

di sini adalah makalah yang lebih baru oleh Raoul Jahin ieeexplore.ieee.org/xpl/…

Marcos Villagra

@MarcosVillagra: SMP sama dengan Note 1 Kaveh, bukan?

Alessandro Cosentino

@Marcos, terima kasih, saya akan memeriksanya, tetapi berdasarkan pada abstrak tampaknya bagi saya bahwa SMP berbeda dari apa yang saya gambarkan. (Saya akan mencoba memberikan contoh yang lebih baik untuk memperjelas bahwa para pemain menggunakan R untuk berkomunikasi yang dapat berlangsung beberapa putaran.) Ps: Saya pikir akan lebih baik jika Anda memposting komentar ini sebagai jawaban.

Kaveh

Jawaban:

Saya yakin Anda tahu makalah berikut, tapi saya tautkan ke sana karena pembaca lain mungkin tertarik: Interpolasi oleh Game

Makalah ini merupakan upaya untuk menggunakan kerangka kompleksitas komunikasi untuk menunjukkan batas bawah untuk memotong pesawat. Protokol digunakan untuk menghasilkan sirkuit interpolant untuk CNF yang tidak memuaskan:

A (x, y) \lor B (x, z) .

$A(x,y)\lor B(x,z).$

Pemain mendapat input dan , pemain mendapat dan . Jika ada bukti seperti pohon dangkal dalam memotong pesawat maka kedua pemain memiliki protokol komunikasi seperti itu $A$ $a$ $y^a$ $B$ $b$ $z^b$

komunikasi apa pun dimediasi oleh wasit, yang membantu mengevaluasi ketidaksetaraan dalam pembuktian;
jumlah komunikasinya kecil (pohonnya dangkal);
kedua pemain memutuskan mana dari atau yang dipalsukan; $A$ $B$
mereka menemukan posisi di mana . $i$ $a_i \not= b_i$

Wasit diubah menjadi protokol probabilistik untuk ketidaksetaraan. Dengan cara ini dimungkinkan untuk mengubah batas bawah untuk protokol probabilistik seperti pohon dalam kerangka kompleksitas komunikasi menjadi batas bawah untuk bukti bidang pemotongan pohon.

Jika kita memiliki batas bawah untuk protokol komunikasi dalam bentuk PLS, maka kita akan mendapatkan batas bawah untuk bukti-bukti pesawat seperti pemotongan dag.

Perhatikan bahwa teknik ini tidak tergantung pada aturan inferensi aktual dari pesawat pemotong. Jika kita menganggap aturan inferensi menjadi (1) kombinasi positif (2) pembagian integer dengan lantai kita dapat membangun monoton sirkuit interpolant menggunakan Pavel Pudlák argumen .

MassimoLauria
sumber

Sebenarnya saya mencoba untuk mencari tahu apakah sesuatu yang lebih umum dari ini telah dipelajari dalam kompleksitas komunikasi, jadi saya tidak menyebutkan kompleksitas bukti lowerbound dan interpolasi yang layak untuk tidak membiaskan jawaban, tapi terima kasih. :)

Kaveh

Ya, saya pikir begitu. Tetapi pembaca lain dari forum ini mungkin tertarik dan mungkin tertarik untuk membuktikan kompleksitas.

MassimoLauria

Hanya beberapa komentar. Pertama, saya tidak mengerti mengapa kita membutuhkan wasit sama sekali. Jika fungsinya dikenal untuk para pemain, mengapa mereka tidak bisa hanya mensimulasikan wasit? Alice mengirimkan ke Bob, ia (tanpa melihat ) menghitung , setelah itu ia menghitung dan memberitahu hasilnya kepada Alice. Mungkin Anda menganggap bahwa yang tidak diketahui Bob, dan ke Alice? $m_A$ $m_A$ $m_B$ $f(m_A,m_B)$ $f_A$ $f_B$

Kedua, protokol yang terkait dengan ketidaksetaraan linear memang menarik dalam konteks pemotongan bukti bidang. Dalam hal ini, bahkan cukup untuk mempertimbangkan protokol, di mana bentuk pesan sangat terbatas : nilai-nilai hanya dari beberapa kombinasi linear dari variabel input dapat dikomunikasikan.

Untuk menjadi sedikit lebih tepat, anggaplah kita diberi sistem ketidaksetaraan linear dengan koefisien integer. Kita tahu bahwa sistem tidak memiliki solusi - . Variabel-variabel itu entah bagaimana terbelah di antara para pemain (dalam lima puluh lima puluh cara); ini adalah skenario "partisi terburuk": musuh dapat memilih partisi "terburuk". Diberikan string - , tujuan para pemain adalah untuk menemukan ketimpangan yang tidak memuaskan. Artinya, jawabannya sekarang bukan sedikit pun, tetapi nama satu ketidaksetaraan sistem kami. (Ini adalah permainan komunikasi jenis Karchmer-Wigderson.) $0$ $1$ $0$ $1$

Sekarang pertimbangkan protokol terbatas berikut untuk permainan seperti itu: (i) fungsi wasit jika hanya iff , (ii) pesan pemain dibatasi untuk yang linier : di setiap putaran, Alice harus mengirim pesan dari formulir , dan Bob pesan dari formulir . $f(\alpha,\beta)=1$ $\alpha \leq \beta$ $m_A(\vec{x})=\vec{c}\cdot \vec{x}$ $m_B(\vec{y})=\vec{d}\cdot \vec{y}$

Impagliazzo, Pitassi dan Urquhart (1994) mengamati hal berikut: Jika semua koefisien yang digunakan dalam pemotongan bidang bukti adalah polinomial dalam jumlah variabel, dan jika permainan ini membutuhkan bit komunikasi, maka setiap pohon seperti bukti ketidakpuasan dari sistem yang diberikan harus menghasilkan ketidaksetaraan . Mereka kemudian menggunakan batas bawah yang diketahui pada kompleksitas komunikasi untuk memberikan sistem eksplisit yang membutuhkan bukti ukuran eksponensial. Kerugian dari hasil ini adalah bahwa sistem ini sangat buatan , tidak ada masalah dengan optimasi "nyata". Oleh karena itu pertanyaan yang menarik untuk muncul dengan batas bawah untuk masalah optimasi "nyata". $t$ $\exp(t/\log n)$

Salah satu masalah tersebut adalah masalah Set Independen untuk grafik. Diberikan grafik kita dapat mengasosiasikan dengan setiap simpul variabel dan mempertimbangkan sistem ketidaksetaraan yang terdiri dari ketidaksetaraan , dan semua ketidaksetaraan untuk semua tepi dari . Karena setiap solusi - untuk subsistem dari ketidaksetaraan yang terakhir ini memberikan set independen dalam , seluruh sistem tidak memiliki solusi nol-satu. Apa kompleksitas komunikasi game untuk sistem seperti itu? $G=(V,E)$ $u$ $x_u$ $\sum_{v\in V}x_v>\alpha(G)$ $x_u+x_v\leq 1$ $uv$ $G$ $0$ $1$ $G$

Jika grafik kami adalah bipartit, maka wajar (untuk musuh) untuk membagi variabel sesuai dengan bagian-bagiannya. Dalam hal ini, Alice mendapat subset , Bob subset dengan janji bahwa . Tujuannya adalah untuk menemukan tepi antara dan . Berikut adalah "bipartit" nomor kemerdekaan: ukuran maksimum set independen tidak bohong sepenuhnya di atau . Salah satu masalah favorit saya adalah: Buktikan bahwa grafik yang membutuhkan bit komunikasi ada . $=(L\cup R,E)$ $A\subseteq L$ $B\subseteq R$ $|A\cup B|>\alpha(G)$ $A$ $B$ $\alpha(G)$ $L$ $R$ $n\times n$ $\omega(\log^2 n)$

@Kaveh: Maaf untuk "menjawab" pertanyaan Anda dengan pertanyaan.

Stasys
sumber

Saya lebih tertarik pada kerangka cc umum daripada aplikasi yang dikenal dalam kompleksitas bukti. Fungsi-fungsi yang digunakan oleh wasit diketahui (mereka diperbaiki seperti yang saya katakan). Ada beberapa masalah mengapa saya tertarik dengan model ini, tetapi poin utamanya adalah tentang bagaimana kita akan mengukur jumlah komunikasi. Jika kami tertarik pada jumlah total bit yang dikomunikasikan maka mungkin untuk mensimulasikan protokol seperti yang Anda katakan. Tetapi jika kita ingin mempertimbangkan beberapa ukuran kompleksitas lainnya seperti jumlah putaran maka saya pikir itu berbeda. Misalnya, dalam satu kasus yang telah digunakan dalam

Kaveh

kompleksitas bukti masing-masing pemain mengirimkan nomor nyata ke wasit. Bilangan real dapat mengkodekan banyak bit, jadi jika Anda ingin mensimulasikan ini, kami harus mengirim bit dalam jumlah tak terbatas, dan jika kami mengizinkannya, kami hanya dapat mengirim seluruh input, sehingga menjadi tidak menarik. Tetapi menghitung jumlah putaran dalam kerangka dengan wasit kita mendapatkan ukuran berbeda yang bisa berguna (seperti dalam bukti Pavel Pudlak).

Kaveh

@ Kaveh: Ya, masuk akal untuk komunikasi apa yang kami hitung. Tetapi dalam bingkai memotong pesawat, kita tidak perlu peduli tentang mengirim bilangan real . Asumsikan saja bahwa semua koefisien adalah bilangan bulat dari ukuran biner ( adalah jumlah variabel). Bahkan ini (dibatasi) kasus tidak jelas, ketika ingin mendapatkan sesuatu untuk "nyata" masalah optimasi (seperti Independen Set). Saya tidak asyik mendapatkan batas bawah untuk "masalah monster". Orang-orang dalam kompleksitas bukti biasanya dipenuhi oleh "monster". Tetapi orang-orang dalam teori optimisasi ingin melihat batas bawah "nyata".

O (\log n)

$O(\log n)$

n

$n$

Stasys

ini adalah masalah sampingan, seperti yang saya katakan ingin tahu lebih banyak tentang jenis kompleksitas komunikasi yang saya jelaskan dalam pertanyaan dan sengaja menghindari menghubungkannya dengan kompleksitas bukti dan interpolasi. Tidak ada yang terkait dengan kompleksitas bukti dalam pernyataan pertanyaan saya.

Kaveh

@Kaveh: Jika fungsi wasit yang diketahui para pemain, saya tidak melihat perbedaan antara ini "protokol wasit" dan "tidak ada protokol wasit" (jika, seperti yang saya katakan, jumlahnya kecil). Perbedaannya dapat terjadi jika kita hanya memiliki satu putaran: pemain mengirim pesan mereka ke wasit, dan dia membuat keputusan akhir. Btw dalam kasus pemain, ini dikenal sebagai "komunikasi pesan simultan". Tentang "masalah monster". Di sini saya berpikir bukan tentang kompleksitas sirkuit, tetapi lebih pada masalah yang dihadapi Teori Optimasi.

k > 2

$k>2$

Stasys