This page is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.
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)
The (correct) phrase "provably unsolvable" has been changed to "probably unsolvable", presumably by people who don't know the subject. Twice I corrected it but I'm sure it will happen again. We need either an article for "provably uncomputable" or a rephrasing: "problems which can be proved unsolvable/uncomputable"? Maybe an affirmative rephrasing like "which problems are computable"? Rcaetano 11:58, 13 Jun 2005 (UTC)
P and NP-complete
P is surely a subset of NP-complete, yes?
Ahh, no, thats an absurd statement to make?! Apologies, profuse and unbounded! I'll come back when I've proved it :-) Grayum 30 June 2005 08:11 (UTC)
I wish you prove it quickly, many of us need to have P=NP proven :-)
It seems to me that most of this article should go in the Complexity Theory page and some in the Computability Theory page. This page should be devoted purely to describing various notions of computation. I am doing some fixup on the computability theory page which is pretty confused so if stuff on this page disappears I probably got far enough alone to move it where it belongs.
This definition is inappropriately restricted to the actions of a computer, rather than more traditional definitions of "computation". For comparison, consider the OED definition: "The action or process of computing, reckoning, or counting; a method or system of reckoning; arithmetical or mathematical calculation." That definition is probably copyrighted and, as such, wouldn't be allowed, but it is properly focused on mathematical evaluation rather than the actions of a computer over time.
In particular, a computation does not necessarily involve the evolution over time of any system; quantum computations may be instantaneous. --bmills 21:25, 22 January 2006 (UTC)
For what it's worth; I agree. —Ruud 22:03, 22 January 2006 (UTC)
What do you mean Quantum computation can be instantenous? Are you sure of that?--Powo 23:02, 22 January 2006 (UTC)
While a quantum computation can take multiple steps, you cannot observe its state during the computation. —Ruud 23:12, 22 January 2006 (UTC)
Quantum computations are not instantaneous; they are most definitely the evolution of a system over time. We may not be able to observe the system until the end of the computation, but that doesn't mean it isn't evolving during the computation. If there is a need for a separate article on more general aspects of computation, perhaps we should fork this into two articles: one on general aspects and one on the kinds of computation studied in computer science. - Gauge 00:21, 23 January 2006 (UTC)
I'd like to keep this article general, the formal computer science definition is already stated in theory of computation. —Ruud 00:30, 23 January 2006 (UTC)
I agree to keep this article general and informal. I would like to keep it focused on computations in the context of CS. From my experience, and in the context of CS, a computation is always the evolution over time of a system, or a mathematical model of such a system. I am interested in counter examples to my POV, but I follow user Gauge in being dubituous that quantum computations are such a counter example, as suggested by user bmills.--Powo 12:24, 23 January 2006 (UTC)
References
I would like to see the references for this article. Where did this text come from? — Dzonatas 20:15, 31 January 2006 (UTC)
