Talk: Computation
From open-encyclopedia.com - the free encyclopedia.
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 and P. 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
- loglogspace is very interesting. It turns out to be the same as a finite automata. The point is that a turning maching with only loglog memory cannot "remember" its entire input, so it's really just a DFA. Maybe this should just be on the DFA page.
Comments by an anonymous person, moved here from the subject page:
- Give an example of problems known or believed to be in each of the above complexity classes.
- Does logspace belong on the above chart?
- What about the Kleene Hierarchy and Oracles?
I don't see a need to give examples of each class, since that would duplicate the examples that can be found by clicking on each class name. It would just duplicate info that's already given elsewhere. --LC 18:23 Sep 13, 2002 (UTC)
Could someone please add a non-circular definition of "computation" and/or "computing" to the article? Perhaps computation is something like "the physical realization of a mathematical function"? --Ryguasu 03:50, 7 Sep 2003 (UTC)
