Предположим, мы хотим объединить два отношения в предикате. Это в NC?
Я понимаю, что доказательство того, что он не находится в NC, будет равносильно доказательству того, что , поэтому я бы принял доказательство того, что это открытая проблема, в качестве ответа.
Меня интересует как общий случай, так и конкретные случаи (например, возможно, с какой-то конкретной структурой данных ее можно распараллелить).
РЕДАКТИРОВАТЬ: внести некоторые пояснения из комментариев в этот пост:
- Мы могли бы рассмотреть эквисоединение . На одном процессоре алгоритм на основе хеша работает в и это лучшее, что мы можем сделать, так как мы должны читать каждый набор
- Если предикат является «черным ящиком», где мы должны проверять каждую пару, естьпары, и каждая из них может быть или нет, так что возможностей. Проверка каждой пары делит возможности пополам, поэтому лучшее, что мы можем сделать, это .
Может ли какой-либо из них (или какой-либо третий тип объединения) быть улучшен до на нескольких процессорах?
Ответы:
источник