Czy sprzężenia mogą być równoległe?

Załóżmy, że chcemy połączyć dwie relacje w predykacie. Czy to jest w NC?

Zdaję sobie sprawę, że dowód, że nie ma go w NC, będzie równoznaczny z dowodem, że , więc przyjmuję dowód, że jest to otwarty problem jako odpowiedź.$P\not=NC$

Interesuje mnie zarówno ogólny przypadek, jak i konkretne przypadki (np. Może z pewną określoną strukturą danych można je zrównoleglić).

EDYCJA: aby wprowadzić wyjaśnienia do komentarzy w tym poście:

• Możemy rozważyć ekwiwalent . Na pojedynczym procesorze algorytm oparty na haszowaniu działa w i jest to najlepsze, co możemy zrobić, ponieważ musimy czytać każdy zestaw$A.x = B.y$$O(|A|+|B|)$
• Jeśli predykatem jest „czarna skrzynka”, w której musimy sprawdzić każdą parę, sąpary, a każda z nich może być lub nie, więc możliwości. Sprawdzanie każdej pary dzieli możliwości na pół, więc najlepiej, co możemy zrobić, to .$|A|\cdot|B|$$2^{ab}$$O(ab)$

Czy któryś z tych (lub jakiś trzeci typ łączenia) mógłby zostać ulepszony do na wielu procesorach?$\log^k n$

$n^2$ procesory mogą porównywać wszystkie możliwości na stałej głębokości, więc tak, jest w NC.${n \choose 2}$