Können Anschlüsse parallelisiert werden?

Question

Angenommen, wir wollen zwei Beziehungen zu einem Prädikat anschließen. Ist das in NC?

Mir ist klar, dass ein Beweis dafür einen Beweis für $ p nicht = nc $ sein würde, daher würde ich Beweise dafür akzeptieren, dass es sich um ein offenes Problem als Antwort handelt.

Ich interessiere mich sowohl für den allgemeinen Fall als auch für bestimmte Fälle (z. B. mit einer spezifischen Datenstruktur kann er parallelisiert werden).

Bearbeiten: Um einige Klarstellungen aus den Kommentaren in diesen Beitrag zu bringen:

• Wir könnten einen Equijoin $ ax = von $ in Betracht ziehen. Bei einem einzelnen Prozessor wird ein Hash-basierter Algorithmus in $ o (| a |+| b |) $ ausgeführt und dies ist das Beste, was wir tun können, da wir jedes Satz lesen müssen
• Wenn das Prädikat ein "schwarzes Feld" ist, in dem wir jedes Paar überprüfen müssen, gibt es $ | a | cdot | b | $ pairs, und jeder könnte in Möglichkeiten oder nicht $ 2^{ab} $ Möglichkeiten sein. Das Überprüfen jedes Paares teilt die Möglichkeiten in zwei Hälften. Das Beste, was wir tun können, ist $ O (AB) $.

Könnte einer von diesen (oder einem dritten Typ von Join) bei mehreren Prozessoren auf $ log^kN $ verbessert werden?

Answer 1

$ n^2 $ Prozessoren können alle $ {n wählen 2} $ Möglichkeiten in konstanter Tiefe, also ist es in NC.