Discusión :
Últimamente he pasado algo de tiempo personal aprendiendo varias cosas en la complejidad de la comunicación. Por ejemplo, me he re-familiarizado con el capítulo relevante en Arora / Barak, comencé a leer algunos documentos y ordené el libro a Kushilevitz / Nisan. Intuitivamente, quiero contrastar la complejidad de la comunicación con la complejidad computacional. Y en particular, me llama la atención el hecho de que la complejidad computacional se ha convertido en una rica teoría de ubicar los problemas computacionales en clases de complejidad, algunas de las cuales pueden ser vistas ( desde una perspectiva, al menos ) en términos de problemas completos para cada clase dada Por ejemplo, al explicar para alguien por primera vez, es difícil evitar comparaciones con SAT o algún otro problema de NP completo.
En comparación, nunca he escuchado nada de un concepto análogo para las clases de complejidad de comunicación. Hay muchos ejemplos que conozco, de problemas "completos para un teorema". Por ejemplo, como un marco general, los autores pueden describir un problema de comunicación dado y luego probar que un teorema relacionado T sostiene i f f el problema de comunicación puede ser resuelto en X o menos bits (para algunos X que depende de la teorema específica / par problemático en cuestión). La terminología utilizada a continuación, en la literatura es que P es "completo" para T .
Además, hay una línea tentadora en el borrador del capítulo de complejidad de comunicación de Arora / Barak (que parece haber sido eliminado / ajustado en la impresión final) que dice "En general, uno puede considerar protocolos de comunicación análogos a , c o N P , P H etc. " Sin embargo, noto dos omisiones importantes:
- El concepto "análogo" parece ser una manera de calcular la complejidad de la comunicación para resolver un protocolo dado con acceso a diferentes tipos de recursos, pero no llega a definir las clases de complejidad de comunicación adecuadas ...
- La mayor parte de la complejidad de la comunicación parece ser relativamente de "bajo nivel", en el sentido de que la abrumadora mayoría de los resultados / teoremas / etc. giran en torno a valores pequeños, específicos, de tamaño polinómico. Esto plantea un poco la pregunta de por qué, por ejemplo, es interesante para el cálculo, pero el concepto análogo parece ser menos interesante para la comunicación. (Por supuesto, podría tener la culpa de no ser consciente de los conceptos de complejidad de comunicación de "nivel superior")
Pregunta (s) :
¿Existe un concepto análogo a las clases de complejidad computacional para la complejidad de la comunicación?
Y:
Si es así, ¿cómo se compara con la noción "estándar" de clases de complejidad? (p. ej., ¿existen limitaciones naturales para las "clases de complejidad de comunicación" que hacen que sean inherentemente inferiores al rango completo de las clases de complejidad computacional?) para la complejidad de la comunicación?
Una sección de Complexity Zoo enumera las clases de Complejidad de comunicación más importantes.
fuente
La razón fundamental por la que existen tales limitaciones en la complejidad de la comunicación es que solo existe una cantidad lineal de información total que necesita ser comunicada (las entradas). Aunque Hartmut Klauck ya lo señaló esencialmente en su respuesta, quería resaltar una respuesta a la otra OQ con respecto a la razón subyacente de esta limitación fundamental, a saber, que los jugadores no tienen límites computacionales .
fuente