結合は平行化できますか？

Question

述語で2つの関係に参加したいとします。これはNCにありますか？

NCにいないことの証拠は、$ p not = nc $の証拠に相当することを理解しているので、答えとして開かれた問題であることの証拠を受け入れます。

私は一般的なケースと特定のケースに興味があります（たとえば、特定のデータ構造を使用すると、並列化できます）。

編集：この投稿にコメントからいくつかの説明をもたらすには：

• Equijoin $ ax = by $を考慮することができます。単一のプロセッサでは、ハッシュベースのアルゴリズムが$ o（| a |+| b |）$で実行されます。これは、各セットを読む必要があるため、できる最善です
• 述語が各ペアをチェックする必要がある「ブラックボックス」である場合、$ | a | cdot | b | $ペアがあり、それぞれが入っているかどうかにかかわらず、$ 2^{ab} $の可能性があります。各ペアをチェックすると、可能性を半分に分割するので、できる最善のことは$ o（ab）$です。

これら（または3番目のタイプの結合）のいずれかを複数のプロセッサで$ log^kn $に改善できますか？

Answer 1

$ n^2 $プロセッサは、すべての$ {n choice 2} $の可能性を一定の深さで比較できますので、はい、それはNCにあります。