Können Verknüpfungen parallelisiert werden?

Angenommen, wir möchten zwei Beziehungen zu einem Prädikat verbinden. Ist das in NC?

Mir ist klar, dass ein Beweis dafür, dass es nicht in NC ist, einem Beweis dafür , dass , also würde ich Beweise dafür akzeptieren, dass es sich um ein offenes Problem handelt.$P\not=NC$

Ich interessiere mich sowohl für den allgemeinen als auch für den speziellen Fall (z. B. kann er mit einer bestimmten Datenstruktur parallelisiert werden).

EDIT: um einige Klarstellungen aus den Kommentaren in diesen Beitrag zu bringen:

• Wir könnten eine äquijoin . Auf einem einzelnen Prozessor wird ein Hash-basierter Algorithmus in Dies ist das Beste, was wir tun können, da wir jeden Satz lesen müssen$A.x = B.y$$O(|A|+|B|)$
• Wenn das Prädikat eine "Black Box" ist, in der jedes Paar überprüft werden muss, gibt esPaare, und jeder könnte in oder nicht sein, also Möglichkeiten. Wenn Sie jedes Paar überprüfen, werden die Möglichkeiten in zwei Hälften geteilt. Das Beste, was wir tun können, ist .$|A|\cdot|B|$$2^{ab}$$O(ab)$

Könnte einer dieser (oder ein dritter Join-Typ) auf mehreren Prozessoren auf verbessert werden ?$\log^k n$

$n^2$ Prozessoren können alle -Möglichkeiten in konstanter Tiefe vergleichen, also ja, es ist in NC.${n \choose 2}$