Talk:Computation
Appearance
I also remember seeing logspace and loglogspace (turning machine with tape restricted to log n or log log n, where n is the input size). I forget where this fits into the above diagram. -209.218.246.2
Polylogspace is a strict subset of PSPACE and strict superset of NC. It is unknown how it compares to P or NP. Logspace is a subset of polylogspace. Loglogspace is a subset of logspace. There are hundreds of complexity classes that have been named in published papers, and logspace / loglogspace wouldn't be in my top 50 of the most interesting. At this point, I'd suggest only adding another class to the list if it's possible to write an article about it that says something interesting. -LC