Pytania otagowane jako communication-complexity

Pytania dotyczące ilości komunikacji potrzebnej do wykonania zadania obliczeniowego, gdy informacje o zadaniu są rozłożone na kilku agentów

2
Gry nielokalne i komunikacja kwantowa
Obecnie szukam dobrych materiałów referencyjnych dotyczących nielokalnych gier o korzystnych aspektach w komunikacji kwantowej. Na przykład jestem świadomy, że gry nielokalne są dobre w ograniczaniu złożoności komunikacji, a także w zapewnieniu bezpieczeństwa protokołów QKD. Chciałbym wiedzieć, jakie są niektóre z wielkich artykułów na temat nielokalnych gier w komunikacji kwantowej? Czy …
1
Dolne granice niedeterministycznej komunikacji wielostronnej
Jest to kontynuacja mojego poprzedniego pytania dotyczącego dolnych granic komunikacji dla częściowych funkcji boolowskich . Czy ktoś może zasugerować jakieś odniesienie do dolnych granic niedeterministycznej komunikacji wielopartyjnej? Przeglądam dokumenty w terenie, ale wydaje się, że wszyscy wykazują separacje następującego typu: dolna granica dla protokołu losowego i (mniejsza) górna granica dla …
1
Problemy z komunikacją, o których nie wiadomo, że istnieje deterministyczne twierdzenie o sumie bezpośredniej
Jest to stary otwarty problem, czy bezpośrednim suma twierdzenie zachodzi dla deterministycznego złożoności komunikacyjnej, to znaczy, czy rozwiązywania niezależnych instancji problemu jest razy twardszy niż rozwiązywanie pojedynczą instancję. [FKNN95] wykazał następujące wyniki:ttttttt Wynik negatywny: istnieje funkcja częściowa (z powodu [O90]), której deterministyczna złożoność komunikacji wynosi , ale obliczenie jej w …
1
Zerowa przypadkowa złożoność komunikacji a deterministyczna złożoność komunikacji
Wiadomo, że dla błędu definicja najgorszego przypadku złożoności losowej komunikacji i definicja średniego przypadku są równoważne. Ale gdy błąd wynosi , najgorszy przypadek złożoności komunikacji losowej jest taki sam, jak deterministyczna złożoność komunikacji.Θ ( 1 )Θ(1)\Theta(1)000 Czy jakaś funkcja ma super-stałą deterministyczną złożoność komunikacji, ale stałą losową złożoność komunikacji przy …
1
Jaka jest największa różnica między rangą a przybliżoną rangą?
Wiemy, że log stopnia macierzy 0-1 jest dolną granicą deterministycznej złożoności komunikacji, a log przybliżonej rangi jest dolną granicą losowości złożoności komunikacji. Największa różnica między deterministyczną złożonością komunikacji a losową złożonością komunikacji ma charakter wykładniczy. A co z różnicą między rangą a przybliżoną rangą macierzy boolowskiej?
1
Zwykłe języki i stała złożoność komunikacji
Pozwolić L⊆A∗L⊆A∗L \subseteq A^* być językiem i zdefiniować fL:A∗×A∗→{0,1}fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\} przez fL(x,y)=1fL(x,y)=1f_L(x, y) = 1 iff x⋅y∈Lx⋅y∈Lx\cdot y \in L. Szukam referencji dla: Propozycja. LLL jest regularna w deterministycznej złożoności komunikacji fLfLf_L jest stały. Innymi słowy, LLL jest normalny iff istnieje protokół dla dwóch graczy …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.