Kompleksitas Komunikasi ... Kelas?

Diskusi :

Saya telah menghabiskan waktu pribadi akhir-akhir ini mempelajari berbagai hal dalam kompleksitas komunikasi. Sebagai contoh, saya telah membiasakan diri dengan bab yang relevan di Arora / Barak, mulai membaca beberapa makalah, dan memesan buku oleh Kushilevitz / Nisan. Secara intuitif, saya ingin membedakan kompleksitas komunikasi dengan kompleksitas komputasi. Dan khususnya, saya dikejutkan oleh kenyataan bahwa kompleksitas komputasi telah berkembang menjadi teori yang kaya dalam menempatkan masalah komputasi ke dalam kelas kompleksitas, beberapa di antaranya dapat pada gilirannya ( dari satu perspektif, setidaknya ) dibayangkan dalam hal masalah lengkap untuk setiap kelas yang diberikan. Misalnya, ketika menjelaskan kepada seseorang untuk pertama kalinya, sulit untuk menghindari perbandingan dengan SAT atau masalah NP-lengkap lainnya.$NP$

Sebagai perbandingan, saya belum pernah mendengar konsep analog untuk kelas kompleksitas komunikasi. Ada banyak contoh yang saya ketahui, masalah "lengkap untuk sebuah teorema." Sebagai contoh, sebagai kerangka kerja umum, penulis dapat menjelaskan masalah komunikasi diberikan dan kemudian membuktikan bahwa teorema terkait berlaku masalah komunikasi dapat diselesaikan dalam atau lebih sedikit bit (untuk beberapa yang tergantung pada teorema / masalah spesifik pasangan dalam pertanyaan). Terminologi yang digunakan maka dalam literatur adalah bahwa adalah "lengkap" untuk .T i f f X X P $P$$T$$iff$$X$$X$$P$$T$

Selanjutnya, ada garis menggoda di Arora / Barak kompleksitas komunikasi bab rancangan (yang tampaknya telah dihapus / tweak dalam pencetakan akhir) yang menyatakan "Pada umumnya, seseorang dapat mempertimbangkan protokol komunikasi analog dengan , , dll " Namun, saya melihat dua kelalaian penting:c o N P P $NP$$coNP$$PH$

1. Konsep "analog" tampaknya menjadi cara komputasi kompleksitas komunikasi untuk menyelesaikan protokol yang diberikan dengan akses ke berbagai jenis sumber daya, tetapi berhenti hanya mendefinisikan kelas kompleksitas komunikasi yang tepat ...
2. Sebagian besar kompleksitas komunikasi tampaknya relatif "tingkat rendah," dalam arti bahwa mayoritas hasil / teorema / dll. berputar di sekitar nilai ish kecil, spesifik, berukuran polinomial. Ini agak menimbulkan pertanyaan mengapa, katakanlah, menarik untuk komputasi tetapi konsep analog tampaknya kurang menarik untuk komunikasi. (Tentu saja, saya bisa saja salah karena tidak menyadari konsep kompleksitas komunikasi "tingkat tinggi".) $NEXP$

Pertanyaan :

Apakah ada konsep analog dengan kelas kompleksitas komputasi untuk kompleksitas komunikasi?

Dan:

Jika demikian, bagaimana perbandingannya dengan gagasan "standar" tentang kelas kompleksitas? (mis. adakah batasan alami untuk "kelas kompleksitas komunikasi" yang menyebabkan mereka secara inheren gagal dalam kisaran penuh kelas kompleksitas komputasi?) Jika tidak, apa alasan "gambaran besar" bahwa kelas adalah formalisme yang menarik untuk kompleksitas komputasi tetapi tidak untuk kompleksitas komunikasi?

Tampaknya Anda mencari makalah ini: http://portal.acm.org/citation.cfm?id=1382439.1382962

Kelas kompleksitas dalam kompleksitas komunikasi diperkenalkan oleh Babai, Frankl, Simon dalam makalah yang dikutip oleh Noam. Makalah ini juga mengembangkan gagasan kelengkapan di bawah pengurangan yang sesuai. Jika Anda misalnya menggambarkan kelas NP dan co-NP itu masuk akal untuk menggambarkan masalah ketidakjelasan (co-NP) juga.

Mengenai pertanyaan kedua Anda, jika P adalah (dalam kompleksitas komunikasi) kelas masalah yang dapat dipecahkan dengan polylog (n) komunikasi secara deterministik, maka kelas EXP haruslah kumpulan masalah yang dapat dipecahkan dengan komunikasi poli (n), yang merupakan segalanya. Jadi sepertinya kelas seperti itu tidak menarik.

Namun, ada cara lain untuk mendapatkan kelas yang lebih besar. Sudah PSPACE didefinisikan (oleh Babai et al.) Bukan dalam hal pengertian ruang, tetapi dalam hal pergantian. Bukti interaktif adalah cara lain untuk mendapatkan kelas kompleksitas besar. Jadi, Anda dapat mendefinisikan kelas MIP sebagai serangkaian masalah yang dapat diselesaikan dalam permainan komunikasi dengan dua prover (yang tidak dapat berbicara satu sama lain) dan dua verifier (yang dapat berbicara satu sama lain dan dengan prover).

Dalam dunia mesin Turing, MIP = NEXP, tetapi bagaimana dengan kompleksitas komunikasi (di mana NEXP tampaknya tidak masuk akal)? Pertama-tama, MIP bukan hanya himpunan semua masalah karena argumen penghitungan yang sederhana.

Andrew Drucker (dalam tesis masternya) telah menunjukkan sesuatu yang menarik tentang kelas ini. Dia menganggap PCP dalam kompleksitas komunikasi, yang (dengan teknik standar) setara dengan protokol MIP (hasilnya sedikit lebih kuat daripada yang saya nyatakan di sini).

Apa yang dia tunjukkan adalah bahwa untuk setiap masalah dalam NP (kelas mesin Turing) dan cara apa pun untuk membagi input, masalah komunikasi yang dihasilkan memiliki protokol MIP dengan polylog komunikasi (n) (yaitu masalahnya ada pada (kompleksitas komunikasi) kelas MIP).

Jadi, sementara MIP bukan segalanya, menemukan masalah eksplisit yang tidak ada di MIP harus sulit (bukan karena kami tidak dapat menemukan masalah yang tidak ada di NP, tetapi karena tidak mudah untuk membayangkan bagaimana kompleksitas mesin Turing dapat ikut berperan. ).

Menunjukkan batas bawah untuk MIP itu sulit seharusnya tidak terlalu mengejutkan, karena kita bahkan tidak tahu bagaimana membuktikan batas bawah untuk protokol AM.

Sebuah bagian dari Zoo Kompleksitas daftar paling kelas Komunikasi Kompleksitas penting.

Alasan mendasar ada pembatasan kompleksitas komunikasi adalah bahwa hanya ada jumlah total informasi linear yang perlu dikomunikasikan (input). Meskipun Hartmut Klauck pada dasarnya telah menunjukkan hal ini dalam jawabannya, saya ingin menyoroti jawaban untuk OQ lain mengenai alasan mendasar dari keterbatasan mendasar ini, yaitu, bahwa para pemain tidak terikat secara komputasi .

$d(n)$$O(d(n)\log n)$$d(n)=O(1)$