with asymptotics; as a result, the algorithm he describes would actually take memory, and time. This means that even for , the algorithm would require more memory than contained on all computers in the world (a kiloexaexaexabyte). Consequences of L = SL The collapse of L and SL has a number of significant consequences. Most obviously, all SL-complete problems are now in L, and can be gainfully employed in the design of deterministic log-space and polylogarithmic-space algorithms. In particular, we have a new set of tools to use in log-space reductions. It is also now known that a problem is in L if and only if it is log-space reducible to USTCON. Footnotes References C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. . Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 . Complexity classes