<i>This algorithm is not only provably computationally hard, but provably requires a lot of RAM</i><p>Almost right.  There is a lower bound on the time-area product, but not a significant lower bound on the area.