可以连接可行?

Question

假如我们想要加入的两个关系上的断言。这是在NC？

我认识到，一个证明它不是在NC将达到一个证明，$P\不=NC$，所以我会接受的证据证明它是一个开放的问题作为一个答案。

我感兴趣的一般情况以及特定情况下(例如也许带一些特定的数据结构可以并行).

编辑：带来一些澄清意见到这个员额：

• 我们可以考虑的一个同等联接$A x=B y$.在一个单一的处理器、一个基于散列算法运行$O(|A|+|B|)美元，这是我们能做的最好，因为我们必须阅读每一组
• 如果主体是"黑箱"里，我们要检查每一对，有$|A|\交通局|B|$对，而且每一个都可能是或不是，所以$2^{ab}$的可能性。检查每一对分歧的可能性的一半，所以最好我们能做的就是$O(ab)$.

可以的这些(或某一第三种类型的参加)，以改善美元\日志^k n$在多个处理器？

Answer 1

$n^2美元处理器可以比较的所有${n\选择2}$的可能性，在恒定深度，所以是的它在NC。