Complexité de la communication avec un arbitre

Supposons un cadre dans la complexité de la communication où nous avons deux joueurs A (poux) et B (ob) et un R (eferee). A et B ne communiquent pas directement entre eux. Dans chaque cycle de communication, chacun d'eux envoie un message ( , ) au R. R calcule deux fonctions et et envoie les résultats pour eux. Les fonctions sont fixes. L'idée est que la communication entre les joueurs est restreinte. De plus, l'arbitre peut effectuer un traitement sur les messages. $m_A$ $m_B$ $f_A(m_A,m_B)$ $f_B(m_A,m_B)$

Exemple:

A et B envoient deux nombres (arbitrairement grands) à R, R vérifie lequel est le plus grand et informe les joueurs.

Dans ce cadre, nous pouvons concevoir un protocole simple qui calcule facilement la fonction suivante en utilisant un seul tour. A et B envoient et à R, R leur renvoie la réponse et ils produisent la réponse. $x$ $y$

f (x, y) = {\begin{cases} 0 & x \leq y \\ 1 & o w \end{cases}

$f(x,y)= \begin{cases}0 & x\leq y\\ 1 & ow \end{cases}$

Évidemment, ce n'est pas un cas intéressant, car la fonction que nous calculons est la même que les fonctions d'arbitre. Un cas plus intéressant est lorsque nous avons une inégalité linéaire fixe et que les valeurs des variables sont réparties entre les joueurs (A a et B a ). La tâche consiste à décider si l'inégalité est correcte. Le protocole dans ce cas est que les joueurs calculent leur part et les envoient ensuite à l'arbitre. $\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$ $\vec{x}$ $\vec{y}$

Question:

Ce type de complexité de communication a-t-il été étudié? Si oui, où puis-je en savoir plus à ce sujet?

note 1: à la page 49 Kushilevitz et Nisan mentionnent un cadre qui implique un arbitre mais semble très différent de ce que je demande.

note 2: Je ne sais pas si appeler R un arbitre est la bonne chose, veuillez commenter si vous avez une meilleure suggestion.

cc.complexity-theory reference-request communication-complexity Kaveh
la source

le modèle que vous mentionnez s'appelle «Passage de message simultané»

Marcos Villagra

consultez cet article ( arxiv.org/abs/quant-ph/0102001 ) et ses références. En particulier, consultez les articles d'Ambainis et de Newman et Szegedy.

Marcos Villagra

voici un article plus récent de Raoul Jahin ieeexplore.ieee.org/xpl/…

Marcos Villagra

@MarcosVillagra: SMP est le même que le Note 1 de Kaveh, n'est-ce pas?

Alessandro Cosentino

@Marcos, merci, je vais les vérifier, mais d'après les résumés, il me semble que SMP est différent de ce que je décris. (Je vais essayer de trouver un meilleur exemple pour montrer clairement que les joueurs utilisent R pour communiquer, ce qui peut prendre plusieurs tours.) Ps: Je pense que ce serait mieux si vous postez ces commentaires comme réponse.

Kaveh

Réponses:

Je suis sûr que vous connaissez l'article suivant, mais j'y ai mis un lien car d'autres lecteurs pourraient être intéressés: Interpolation par Games

Cet article est une tentative d'utiliser le cadre de complexité de la communication pour montrer les limites inférieures des plans de coupe. Le protocole est utilisé pour produire un circuit interpolant pour CNF insatisfaisant:

A (x, y) \lor B (x, z) .

$A(x,y)\lor B(x,z).$

Le joueur reçoit l'entrée et , le joueur obtient et . S'il y a une preuve peu profonde en forme d'arbre dans les plans de coupe, les deux joueurs ont un protocole de communication tel que $A$ $a$ $y^a$ $B$ $b$ $z^b$

toute communication est médiée par l'arbitre, ce qui aide à évaluer les inégalités dans la preuve;
la quantité de communication est petite (l'arbre est peu profond);
les deux joueurs décident lequel de ou est falsifié; $A$ $B$
ils trouvent une position dans laquelle . $i$ $a_i \not= b_i$

L'arbitre est transformé en un protocole probabiliste des inégalités. De cette façon, il est possible de transformer la borne inférieure pour les protocoles probabilistes arborescents dans le cadre de complexité de la communication en borne inférieure pour les preuves de plans de coupe arborescents.

Si nous avions une borne inférieure pour le protocole de communication sous la forme d'un PLS, alors nous aurions une borne inférieure pour les preuves des plans de coupe en forme de dag.

Notez que cette technique ne dépend pas des règles d'inférence réelles des plans de coupe. Si nous supposons que les règles d'inférence sont (1) une combinaison positive (2) une division entière avec le plancher, nous pouvons construire le circuit d'interpolation monotone en utilisant l' argument de Pavel Pudlák .

MassimoLauria
la source

En fait, j'essayais de comprendre si quelque chose de plus général que cela a été étudié dans la complexité de la communication, donc je n'ai pas mentionné les limites inférieures de la complexité de la preuve et l'interpolation faisable pour ne pas biaiser les réponses, mais merci. :)

Kaveh

Oui, je le pensais. Mais d'autres lecteurs de ce forum peuvent être intéressés et peuvent s'intéresser à la preuve de la complexité.

MassimoLauria

$m_A$ $m_A$ $m_B$ $f(m_A,m_B)$ $f_A$ $f_B$

Deuxièmement, les protocoles liés aux inégalités linéaires sont en effet intéressants dans le cadre de la coupe des preuves planes. Dans ce cas, il suffit même de considérer des protocoles, où la forme des messages est très restreinte : seules les valeurs de certaines combinaisons linéaires de variables d'entrée peuvent être communiquées.

$0$ $1$ $0$ $1$

$f(\alpha,\beta)=1$ $\alpha \leq \beta$ $m_A(\vec{x})=\vec{c}\cdot \vec{x}$ $m_B(\vec{y})=\vec{d}\cdot \vec{y}$

$t$ $\exp(t/\log n)$

$G=(V,E)$ $u$ $x_u$ $\sum_{v\in V}x_v>\alpha(G)$ $x_u+x_v\leq 1$ $uv$ $G$ $0$ $1$ $G$

$=(L\cup R,E)$ $A\subseteq L$ $B\subseteq R$ $|A\cup B|>\alpha(G)$ $A$ $B$ $\alpha(G)$ $L$ $R$ $n\times n$ $\omega(\log^2 n)$

@Kaveh: Désolé d'avoir "répondu" à votre question avec des questions.

Stasys
la source

Je m'intéresse plus au framework cc général qu'à ses applications connues en complexité de preuve. Les fonctions utilisées par l'arbitre sont connues (elles sont fixes comme je l'ai dit). Il y a un certain nombre de problèmes pour lesquels je suis intéressé par ce modèle, mais le point principal est de savoir comment nous allons mesurer la quantité de communication. Si nous sommes intéressés par le nombre total de bits communiqués, il est possible de simuler le protocole comme vous l'avez dit. Mais si nous voulons considérer d'autres mesures de complexité comme le nombre de tours, je pense que c'est différent. Par exemple, dans un cas qui a été utilisé dans

Kaveh

complexité de la preuve chaque joueur envoie un nombre réel à l'arbitre. Un nombre réel peut coder une infinité de bits, donc si vous voulez simuler cela, nous devons envoyer un nombre infini de bits, et si nous l'autorisons, nous pouvons simplement envoyer la totalité de l'entrée, ce qui devient inintéressant. Mais en comptant le nombre de tours dans le cadre avec un arbitre, nous obtenons une mesure différente qui peut être utile (comme dans la preuve de Pavel Pudlak).

Kaveh

O (\log n)

$O(\log n)$

n

$n$

ce sont des problèmes secondaires, comme je l'ai dit, je veux en savoir plus sur le type de complexité de communication que j'ai décrit dans la question et j'ai intentionnellement évité de le lier à la complexité de la preuve et aux interpolations. Il n'y a rien de lié à la complexité de la preuve dans l'énoncé de ma question.

Kaveh

k > 2

$k>2$