As junções podem ser paralelizadas?

Suponha que desejemos unir duas relações em um predicado. Isso está no NC?

Percebo que uma prova de que não está na NC equivaleria a uma prova de que , então aceitaria a evidência de que é um problema em aberto como resposta.$P\not=NC$

Estou interessado no caso geral e também nos casos específicos (por exemplo, talvez com alguma estrutura de dados específica, ela possa ser paralelizada).

EDIT: para trazer alguns esclarecimentos dos comentários para este post:

• Poderíamos considerar um equijoin . Em um único processador, um algoritmo baseado em hash é executado em e é o melhor que podemos fazer, pois precisamos ler cada conjuntoO ( | A | + | B |$A.x = B.y$$O(|A|+|B|)$
• Se o predicado é uma "caixa preta" onde temos que verificar cada par, existempares, e cada um poderia estar dentro ou não, então possibilidades. Verificar cada par divide as possibilidades pela metade, então o melhor que podemos fazer é .2 a b O ( a b $|A|\cdot|B|$$2^{ab}$$O(ab)$

Um desses (ou algum terceiro tipo de junção) poderia ser aprimorado para em vários processadores?$\log^k n$

$n^2$ processadores podem comparar todas as possibilidades de em profundidade constante; portanto, sim, está em NC.${n \choose 2}$