Ejercicio 3.a Ob 2

Ejercicio 3.a Ob 2

de Luis Pedro Bonomi Vigil -
Número de respuestas: 2

Buenas,

En este ejercicio se pide probar que la multiplicación de las matrices booleanas se puede hacer en espacio logarítmico. Se dice que todas las matrices son nxn, por lo tanto si queremos ir multiplicando celda por celda precisamos dos índices, uno para la fila y otro para la columna, que serían de tamaño n. Entonces se tiene que el espacio necesario para guardar los índices tiene O(sqrt(x)) (ya que n = sqrt(nxn)) y como sqrt(x) crece más rápido que log(x) pienso que no es posible que se haga el problema en espacio logarítmico. ¿Es esto posible?

Saludos,
Luis Pedro

En respuesta a Luis Pedro Bonomi Vigil

Re: Ejercicio 3.a Ob 2

de Alex Elenter Litwin -
Buenas,
Te cuento porque pienso que falla tu razonamiento y si el Tuba o Julian puede confirmar o corregir barbaro. Para guardar un indice no precisas algo del orden de la matriz, si no que con log("tam de la matriz") te basta. Pensa por ejemplo cuantos bits precisas para indexar una tira de n bits, esto claramente son log(n) bits, ya que podes contar desde 0 a 2^(log(n)) = n.
Saludos,