Les jointures peuvent-elles être parallélisées?

Supposons que nous voulons joindre deux relations sur un prédicat. Est-ce en NC?

Je me rends compte qu'une preuve qu'il n'est pas en NC équivaudrait à une preuve que $P\not=NC$ , donc j'accepterais comme preuve un problème ouvert comme réponse.

Je m'intéresse au cas général ainsi qu'aux cas spécifiques (par exemple avec une structure de données spécifique, il peut être parallélisé).

EDIT: pour apporter quelques clarifications des commentaires dans ce post:

• Nous pourrions envisager une équijointure $A.x = B.y$ . Sur un seul processeur, un algorithme basé sur le hachage s'exécute en $O(|A|+|B|)$ et c'est le mieux que nous puissions faire car nous devons lire chaque ensemble
• Si le prédicat est une "boîte noire" où nous devons vérifier chaque paire, il y a $|A|\cdot|B|$paires, et chacun pourrait être ou non, donc $2^{ab}$ possibilités. Vérifier chaque paire divise les possibilités en deux, donc le mieux que nous puissions faire est $O(ab)$ .

L'un de ceux-ci (ou un troisième type de jointure) pourrait-il être amélioré pour se sur plusieurs processeurs?$\log^k n$

processeurs peuvent tout comparer ($n^2$ possibilités en profondeur constante, donc oui c'est en NC.${n \choose 2}$