Złożoność komunikacji… Klasy?

Dyskusja :

Spędziłem ostatnio trochę czasu na nauce różnych rzeczy w złożoności komunikacji. Na przykład ponownie zapoznałem się z odpowiednim rozdziałem w Arora / Barak, zacząłem czytać kilka artykułów i zamówiłem książkę Kushilevitz / Nisan. Intuicyjnie chcę porównać złożoność komunikacji ze złożonością obliczeniową. W szczególności uderza mnie fakt, że złożoność obliczeniowa przekształciła się w bogatą teorię umieszczania problemów obliczeniowych w klasach złożoności, z których niektóre można z kolei ( przynajmniej z jednej perspektywy ) przewidzieć w kategoriach kompletnych problemów dla każda podana klasa. Na przykład, wyjaśniając komuś po raz pierwszy, trudno jest uniknąć porównań z SAT lub innym problemem z NP-zupełnym.$NP$

Dla porównania nigdy nie słyszałem o analogicznej koncepcji klas złożoności komunikacji. Znam wiele przykładów problemów „gotowych na twierdzenie”. Na przykład, jako ogólne ramy, autorzy mogą opisać problem komunikacji daną , a następnie udowodnić, że powiązany twierdzenie posiada problem komunikacyjny może być rozwiązany w lub mniej bitów (dla niektórych , który zależy od konkretnego twierdzenia / problemu para, o której mowa). Terminologia stosowana to w literaturze, że jest „pełny” w .T i f f X X P $P$$T$$iff$$X$$X$$P$$T$

Ponadto w szkicu rozdziału złożoności komunikacji Arora / Barak znajduje się kusząca linia (która wydaje się, że została usunięta / poprawiona w ostatecznym druku), która stwierdza: „Ogólnie rzecz biorąc, można rozważyć protokoły komunikacyjne analogiczne do , , itp. „ Widzę jednak dwa ważne pominięcia:c o N P P $NP$$coNP$$PH$

1. Koncepcja „analogiczna” wydaje się być sposobem na obliczenie złożoności komunikacyjnej rozwiązania danego protokołu z dostępem do różnych rodzajów zasobów, ale przestaje definiować odpowiednie klasy złożoności komunikacyjnej ...
2. Większość złożoności komunikacji wydaje się być względnie „na niskim poziomie” w tym sensie, że przeważająca większość wyników / twierdzeń / itp. obracają się wokół małych, specyficznych, wielomianowych wartości. To rodzi pytanie, dlaczego, powiedzmy, jest interesujący w obliczeniach, ale analogiczna koncepcja wydaje się mniej interesująca w komunikacji. (Oczywiście mógłbym być winny, że nie jestem świadomy koncepcji złożoności komunikacji „wyższego poziomu”). $NEXP$

Pytanie (pytania) :

Czy istnieje koncepcja analogiczna do obliczeniowych klas złożoności dla złożoności komunikacyjnej?

I:

Jeśli tak, to jak to porównać ze „standardowym” pojęciem klas złożoności? (np. czy istnieją naturalne ograniczenia dla „klas złożoności komunikacyjnej”, które powodują, że z natury rzeczy nie mieszczą się one w pełnym zakresie klas złożoności obliczeniowej?) Jeśli nie, to jaki jest „ogólny obraz” powodu, że klasy są interesującym formalizmem dla złożoności obliczeniowej, ale nie dla złożoności komunikacji?

Wygląda na to, że szukasz tego papieru: http://portal.acm.org/citation.cfm?id=1382439.1382962

Klasy złożoności w złożoności komunikacyjnej zostały wprowadzone przez Babai, Frankl, Simon w artykule cytowanym przez Noama. Artykuł rozwija także ideę kompletności przy odpowiednich redukcjach. Jeśli na przykład opisujesz klasy NP i co-NP, sensowne jest również opisanie problemu (rozłączenia co-NP).

Jeśli chodzi o twoje drugie pytanie, jeśli P jest (pod względem złożoności komunikacyjnej) klasą problemów rozwiązanych za pomocą komunikacji polilog (n) deterministycznie, to klasa EXP powinna być zbiorem problemów rozwiązanych za pomocą komunikacji poli (n), co jest po prostu wszystkim. Wygląda więc na to, że takie zajęcia nie są interesujące.

Istnieje jednak inny sposób na uzyskanie większych klas. Już PSPACE jest zdefiniowany (przez Babai i in.) Nie w kategoriach jakiegoś pojęcia przestrzeni, ale w kategoriach naprzemienności. Interaktywne proofy to kolejny sposób na uzyskanie dużych klas złożoności. Możesz więc zdefiniować MIP klasy jako zestaw problemów, które można rozwiązać w grze komunikacyjnej z dwoma dowódcami (którzy nie mogą ze sobą rozmawiać) i dwoma weryfikatorami (którzy mogą ze sobą rozmawiać i dowódcami).

W świecie maszyn Turinga MIP = NEXP, ale co ze złożonością komunikacji (gdzie NEXP wydaje się nie mieć sensu)? Po pierwsze, MIP to nie tylko zestaw wszystkich problemów z powodu prostego argumentu liczenia.

Andrew Drucker (w swojej pracy magisterskiej) pokazał coś interesującego w tej klasie. Uważa PCP za złożoność komunikacji, która (zgodnie ze standardowymi technikami) jest równoważna protokołom MIP (jego wynik jest nieco silniejszy niż to, co tu stwierdzam).

Pokazuje, że dla każdego problemu w NP (klasa maszyny Turinga) i każdego sposobu podziału danych wejściowych wynikowy problem komunikacyjny ma protokół MIP z polilogiem komunikacyjnym (n) (tzn. Problem jest związany z (złożonością komunikacji) klasa MIP).

Tak więc, chociaż MIP to nie wszystko, znalezienie wyraźnego problemu, którego nie ma w MIP, powinno być trudne (nie dlatego, że nie możemy znaleźć problemów, których nie ma w NP, ale dlatego, że niełatwo jest wyobrazić sobie, jak złożona może być złożoność maszyny Turinga ).

To, że pokazywanie dolnych granic dla MIP jest trudne, nie powinno być zbyt zaskakujące, ponieważ nawet nie wiemy, jak udowodnić dolne granice dla protokołów AM.

Odcinek Zoo Complexity wymienia najważniejsze zajęcia Komunikacja złożoności.

Podstawowym powodem takich ograniczeń w złożoności komunikacji jest to, że zawsze istnieje tylko liniowa ilość całkowitej informacji, którą należy przekazać (dane wejściowe). Chociaż Hartmut Klauck już zasadniczo wskazał na to w swojej odpowiedzi, chciałem zwrócić uwagę na inne OQ dotyczące podstawowej przyczyny tego fundamentalnego ograniczenia, a mianowicie, że gracze są obliczeniowo nieograniczeni .

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