Puede ser parallelized une?

Question

Supongamos que queremos unir dos relaciones en un predicado. ¿Es esto en Carolina del Norte?

Me doy cuenta de que una prueba de que no fuera en NC equivaldría a una prueba de que $ P \ = No NC $, así que aceptaría la evidencia de que sea un problema abierto como respuesta.

Estoy interesado en el caso general, así como casos específicos (por ejemplo, tal vez con alguna estructura de datos específica que se puede paralelizar).

EDIT: para traer algunas aclaraciones a los comentarios en este post:

• Se podría considerar una combinación de igualdad A.x $ = $ B.y. En un único procesador, una basada en hash algoritmo se ejecuta en $ O (| a | + | B |) $ y esto es lo mejor que podemos hacer ya que tenemos que leer cada conjunto
• Si el predicado es un "recuadro negro", donde tenemos que comprobar cada par, hay $ | A | \ cdot | B | $ pares, y cada uno puede ser o no, por lo que $ 2 ^ {ab} $ posibilidades. Comprobación de cada par divide las posibilidades en la mitad, por lo que lo mejor que podemos hacer es $ O (ab) $.

Podría cualquiera de estos (o un tercer tipo de unión) se mejoró a $ \ log ^ k $ n en varios procesadores?

Answer 1

$ n ^ 2 procesadores $ puede comparar todos $ {n \ choose 2} $ posibilidades en profundidad constante, por lo que sí que está en Carolina del Norte.