Можно ли параллелизировать соединения?

Question

Предположим, мы хотим присоединиться к двум отношениям на предикате. Это в NC?

Я понимаю, что доказательство того, что он отсутствует в NC, будет подтвержден доказательством того, что $ p not = nc $, поэтому я бы принял доказательства того, что это является открытой проблемой в качестве ответа.

Я заинтересован в общем случае, а также в конкретных случаях (например, возможно, с некоторой конкретной структурой данных, это может быть параллельно).

РЕДАКТИРОВАТЬ: Чтобы принести некоторые пояснения из комментариев в этом посте:

• Мы могли бы рассмотреть эквиноин $ ax = $. На одном процессоре алгоритм на основе хэша работает в $ O (| A |+| B |) $, и это лучшее, что мы можем сделать, так как мы должны прочитать каждый набор
• Если предикат - это «черный ящик», где мы должны проверить каждую пару, есть пары $ | a | cdot | b | $, и каждый из них может быть в или нет, так что $ 2^{ab} $ возможностей. Проверка каждой пары делит возможности пополам, так что лучшее, что мы можем сделать, это $ O (ab) $.

Можно ли улучшить любой из них (или какой -то третий тип соединения) до $ log^kn $ на нескольких процессорах?

Answer 1

$ n^2 $ Процессоры могут сравнивать все $ {n Выберите 2} $.