Peut être parallélisé se joint?

Question

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

Je me rends compte qu'une preuve de ce ne pas être en NC constituerait une preuve que $ P \ not = NC $, donc je l'accepte la preuve de ce être un problème ouvert comme une réponse.

Je suis intéressé dans le cas général, ainsi que des cas particuliers (par exemple peut-être avec une certaine structure de données spécifique, il peut être parallélisé).

EDIT: pour apporter quelques éclaircissements des commentaires dans ce message:

• Nous pourrions envisager une équijointure $ A.x = B.y $. Sur un seul processeur, un algorithme basé sur le hachage fonctionne dans O $ (| A | + | B |) $ et c'est le meilleur que nous pouvons faire, puisque 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 pas, donc 2 $ ^ {ab} $ possibilités. Vérification de chaque paire divise les possibilités de moitié, de sorte que le mieux que nous puissions faire est de O $ (ab) $.

pourrait l'une de ces (ou un troisième type de jointure) être amélioré à $ \ log ^ k n $ sur plusieurs processeurs?

Answer 1

$ n ^ 2 processeurs $ peut comparer $ {n \ choose 2} $ possibilités en profondeur constante, donc oui il est en Caroline du Nord.