Talk:Computation/Archive 1

From Wikipedia, the free encyclopedia

Archive This 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 :-)
King Mike 21:14, 22 November 2005 (UTC)

Computation vs. Computability Theory

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.


Logicnazi 05:24, 23 October 2005 (UTC)