Timeline for Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)
Current License: CC BY-SA 4.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 10, 2019 at 19:06 | comment | added | Pierrot | Thank you very much for your kind reply. If the intermediate matrices don't need to be stored anywhere, I don't understand the algorithm that let compute $A^p$ in $O(\log n\log p)$ space. | |
| Dec 10, 2019 at 8:30 | history | answered | D.W.♦ | CC BY-SA 4.0 |