Communication complexity (original) (raw)
Die Kommunikationskomplexität ist ein Teilgebiet der Komplexitätstheorie und wird angewendet um die Frage zu untersuchen, wie viel Kommunikation zum Lösen bestimmter Aufgaben nötig ist, wobei die Eingabe auf mehrere Rechner verteilt ist. Das Hauptaugenmerk liegt dabei auf der Anzahl der Bits, die zwischen den Rechnern versendet werden müssen, damit diese die ihnen gestellte Aufgabe erfüllen können. Die Kommunikationskomplexität ist ein Werkzeug der theoretischen Informatik, insbesondere beim Beweis von unteren Schranken für den Ressourcenbedarf von Berechnungen.
| Property | Value |
|---|---|
| dbo:abstract | Die Kommunikationskomplexität ist ein Teilgebiet der Komplexitätstheorie und wird angewendet um die Frage zu untersuchen, wie viel Kommunikation zum Lösen bestimmter Aufgaben nötig ist, wobei die Eingabe auf mehrere Rechner verteilt ist. Das Hauptaugenmerk liegt dabei auf der Anzahl der Bits, die zwischen den Rechnern versendet werden müssen, damit diese die ihnen gestellte Aufgabe erfüllen können. Die Kommunikationskomplexität ist ein Werkzeug der theoretischen Informatik, insbesondere beim Beweis von unteren Schranken für den Ressourcenbedarf von Berechnungen. (de) In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines.The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them. While Alice and Bob can always succeed by having Bob send his whole -bit string to Alice (who then computes the function ), the idea here is to find clever ways of calculating with fewer than bits of communication. Note that, unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we generally assume nothing about the computational power of either Alice or Bob. This abstract problem with two parties (called two-party communication complexity), and its general form with more than two parties, is relevant in many contexts. In VLSI circuit design, for example, one seeks to minimize energy used by decreasing the amount of electric signals passed between the different components during a distributed computation. The problem is also relevant in the study of data structures and in the optimization of computer networks. For surveys of the field, see the textbooks by and . (en) La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages. Utiliser une ressources en communication est le fait d'envoyer une information à l'autre. Alice peut ainsi envoyer la première lettre de son mot à bob, ceci a un coût de 1. La théorie de la complexité de communication a donc pour but de calculer quelles sont les ressources en communication nécessaires pour effectuer certaines tâches dans un contexte de calcul distribué. Contrairement à la théorie de la complexité classique, on ne compte pas les ressources nécessaires aux calculs (temps et espace par exemple). Cette notion a été définie en 1979 par Andrew Yao et est utilisée notamment pour l'étude des algorithmes en ligne et le design des circuits VLSI. (fr) 通信複雑性（つうしんふくざつせい、Communication Complexity、CC）は、1979年にアンドリュー・チーチー・ヤオによって導入された用語である。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。 もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。 この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。 (ja) В теоретической информатике коммуникационная сложность изучает количество коммуникации, необходимое для решения задачи, параметры которой распределены между двумя или более сторонами. Это понятие было введено Эндрю Яо в 1979 году, который исследовал следующую задачу для двух участников, традиционно называемых Алисой и Бобом. Алиса получает n-битную строку x, а Bob — n-битную строку y, и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию , при этом с наименьшим количеством коммуникации между ними. Конечно, они всегда могут вычислить следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет функцию . Поэтому в данной постановке задачи интересно, для каких функций f существует способ вычислить передав менее n битов. Важное отметить, что в данной задаче нас не интересует сложность вычислений, выполненных Алисой или Бобом, или размер используемой для этих вычислений памяти. Эта абстрактная проблема с двумя участниками (называемая коммуникационной сложностью с двумя участниками) и ее общая форма с большим количеством участников возникает в различных областях компьютерных наук: например, при проектировании схем больших интегральных схем требуется минимизировать используемую энергию, путём уменьшения количества электрических сигналов между различными компонентами во время распределенных вычислений. Коммуникационная сложность используется также при изучении структур данных и алгоритмов, при оптимизации компьютерных сетей, в теории вычислительной сложности и сложности доказательств и в других областях. (ru) A noção de complexidade de comunicação foi introduzida por em 1979,que investigou o seguinte problema envolvendo duas partes (Alice e Bob). Alice recebe uma cadeia x de n bits e Bob outra cadeia y de n bits, e o objetivo é que um deles (digamos, Bob) compute uma certa função f(x,y) com a menor quantidade de comunicação entre eles. Note que não estamos preocupados com o número de passos da computação, ou com o tamanho da memória (informática) utilizada. Complexidade de comunicação tenta quantificar quanta comunicação é necessário para essas computações distribuídas. Claro que eles podem conseguir com Alice enviando sua cadeia inteira para Bob, que então computa a função, mas a ideia aqui é encontrar maneiras inteligentes de calcular f com menos de n bits de comunicação. Esse problema abstrato é relevante em vários contextos: no design de circuitos VSLI, por exemplo, deseja-se minimizar a energia utilizada diminuindo a quantidade de sinal elétricos necessários entre os diferentes componentes durante uma computação distribuída. O problema também é relevante no estudo de estruturas de dados, e na otimização de redes de computadores. Para um panorama da área, veja o livro de Kushilevitz e Nisan. (pt) |
| dbo:wikiPageExternalLink | https://arxiv.org/abs/quant-ph/0101005 http://u.cs.biu.ac.il/~zarosih/70/files/private_vs__common_random_bits_in_commun_493418.pdf https://www.sciencedirect.com/science/article/pii/S030439759600062X/pdf%3Fmd5=673842d5f5b8a83d07e2c183ffa357a1&pid=1-s2.0-S030439759600062X-main.pdf&_valck=1 |
| dbo:wikiPageID | 50329 (xsd:integer) |
| dbo:wikiPageLength | 26060 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1108502621 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Protocol_(computing) dbr:Quantum_entanglement dbr:Qubit dbr:Alice_and_Bob dbr:VLSI dbr:Matrix_(mathematics) dbr:Multiparty_communication_complexity dbr:Function_(mathematics) dbr:Photons dbr:Andrew_Yao dbr:Communication dbr:Computational_complexity dbr:Computational_complexity_theory dbr:Computer_memory dbr:Theoretical_computer_science dbr:Gap-Hamming_problem dbr:Space–time_tradeoff dbr:Finite_field dbr:Rank_(linear_algebra) dbc:Quantum_complexity_theory dbc:Computational_complexity_theory dbr:Bit dbr:Hoeffding's_inequality dbr:Dot_product dbc:Communication dbr:Optical_fiber dbr:Ran_Raz dbr:Distributed_computation dbr:Nonnegative_rank_(linear_algebra) dbr:Streaming_algorithms dbr:Submatrix dbr:VLSI_circuit dbr:Decision_tree_complexity |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Harvtxt dbt:Mvar dbt:Reflist dbt:Short_description dbt:Tmath dbt:Use_American_English dbt:Val |
| dct:subject | dbc:Quantum_complexity_theory dbc:Computational_complexity_theory dbc:Communication |
| rdfs:comment | Die Kommunikationskomplexität ist ein Teilgebiet der Komplexitätstheorie und wird angewendet um die Frage zu untersuchen, wie viel Kommunikation zum Lösen bestimmter Aufgaben nötig ist, wobei die Eingabe auf mehrere Rechner verteilt ist. Das Hauptaugenmerk liegt dabei auf der Anzahl der Bits, die zwischen den Rechnern versendet werden müssen, damit diese die ihnen gestellte Aufgabe erfüllen können. Die Kommunikationskomplexität ist ein Werkzeug der theoretischen Informatik, insbesondere beim Beweis von unteren Schranken für den Ressourcenbedarf von Berechnungen. (de) 通信複雑性（つうしんふくざつせい、Communication Complexity、CC）は、1979年にアンドリュー・チーチー・ヤオによって導入された用語である。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。 もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。 この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。 (ja) In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines.The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them. (en) La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages. (fr) A noção de complexidade de comunicação foi introduzida por em 1979,que investigou o seguinte problema envolvendo duas partes (Alice e Bob). Alice recebe uma cadeia x de n bits e Bob outra cadeia y de n bits, e o objetivo é que um deles (digamos, Bob) compute uma certa função f(x,y) com a menor quantidade de comunicação entre eles. Note que não estamos preocupados com o número de passos da computação, ou com o tamanho da memória (informática) utilizada. Complexidade de comunicação tenta quantificar quanta comunicação é necessário para essas computações distribuídas. (pt) В теоретической информатике коммуникационная сложность изучает количество коммуникации, необходимое для решения задачи, параметры которой распределены между двумя или более сторонами. Это понятие было введено Эндрю Яо в 1979 году, который исследовал следующую задачу для двух участников, традиционно называемых Алисой и Бобом. Алиса получает n-битную строку x, а Bob — n-битную строку y, и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию , при этом с наименьшим количеством коммуникации между ними. Конечно, они всегда могут вычислить следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет функцию . Поэтому в данной постановке задачи интересно, для каких функций f существует способ вычислить (ru) |
| rdfs:label | Kommunikationskomplexität (de) Communication complexity (en) Complexité de la communication (fr) 通信複雑性 (ja) Complexidade de comunicação (pt) Коммуникационная сложность (ru) |
| owl:sameAs | freebase:Communication complexity wikidata:Communication complexity dbpedia-de:Communication complexity dbpedia-fr:Communication complexity dbpedia-he:Communication complexity dbpedia-ja:Communication complexity dbpedia-pt:Communication complexity dbpedia-ru:Communication complexity dbpedia-tr:Communication complexity dbpedia-vi:Communication complexity https://global.dbpedia.org/id/4iHVZ |
| prov:wasDerivedFrom | wikipedia-en:Communication_complexity?oldid=1108502621&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Communication_complexity |
| is dbo:academicDiscipline of | dbr:Jaikumar_Radhakrishnan |
| is dbo:knownFor of | dbr:Harry_Buhrman dbr:Ronald_de_Wolf |
| is dbo:wikiPageRedirects of | dbr:Quantum_communication_complexity |
| is dbo:wikiPageWikiLink of | dbr:Proof_complexity dbr:Proof_of_secure_erasure dbr:Alon_Orlitsky dbr:List_of_pioneers_in_computer_science dbr:Jaikumar_Radhakrishnan dbr:Matrix_norm dbr:Oded_Regev_(computer_scientist) dbr:Quantum_nonlocality dbr:Multiparty_communication_complexity dbr:Concentration_inequality dbr:Andrew_Yao dbr:Computational_complexity_theory dbr:Harry_Buhrman dbr:Theoretical_computer_science dbr:Active_networking dbr:Centre_for_Quantum_Technologies dbr:Turing_Award dbr:Distributed_computing dbr:Gap-Hamming_problem dbr:Log-rank_conjecture dbr:Predecessor_problem dbr:Rank_(linear_algebra) dbr:Szemerédi_regularity_lemma dbr:Ashok_K._Chandra dbr:Hidden_Matching_Problem dbr:Greenberger–Horne–Zeilinger_state dbr:Randomized_algorithm dbr:Exponential_time_hypothesis dbr:Streaming_algorithm dbr:Picking_sequence dbr:S2S_(mathematics) dbr:Ronald_de_Wolf dbr:Quantum_communication_complexity |
| is dbp:field of | dbr:Jaikumar_Radhakrishnan |
| is dbp:knownFor of | dbr:Ronald_de_Wolf |
| is foaf:primaryTopic of | wikipedia-en:Communication_complexity |