Content deleted Content added
→Merge notices: merge merge merge |
→Merge notices: suggestion for articles |
||
Line 44:
:: I think you could define what a '''resource''' bound is in terms of big-O and whatnot, and then define DTIME to be a bound on runtime, DSPACE a bound on space. Maybe also insert other bounds, like communication (not sure regarding the exact name/definition of communication complexity). I agree most individual complexity classes (and there are tons of them) do not belong here, but this is part of the very definition of complexity class. On a side note, what do you think about changing the name from DTIME to Time Complexity. Hmm, after writing this line, I went and checked the article on "Time complexity" ... guess what - it's a redirect here (although Space complexity is a dictionary definition and should be removed. I replaced it with a redirect here for now). [[User:Ripper234|Ripper234]] 16:56, 4 April 2006 (UTC)
:I'm a little bit confused by your post. DTIME and DSPACE are not "part of the very definition of complexity classes"; they're computation resources on a ''specific model'' of abstract machine. You seem to be confusing them with [[computation time]] and [[memory space]], which hold on almost any model of Turing machine (nondeterministic, conondeterministic, quantum, probabilistic, whatever). I'd be happy to change the name from "DTIME" to "Deterministic time", but I really believe that "computation time" should be a separate article. My vision for this hierarchy of articles is:
:*[[Computation time]] describes "the number of steps on (any kind of) Turing machine", and talks about the various time-complexity classes on different abstract machines. Compares DTIME and NTIME, etc.
:*[[DTIME]] describes computation time on a ''deterministic machine''. Talks about the deterministic-time hierarchy, the classes defined in terms of deterministic time, relationship to other resources, etc.
:*[[P (complexity)|P]] describes the specific complexity class of ''polynomial amount of DTIME''. Talks about complete problems, applications to feasibility, relations to other classes.
:*[[Deterministic Turing machine]] describes the ''model'' of abstract machine, and goes somewhat into the time and space complexity classes, and how the model relates to other models.
:All of these concepts are separate. They are studied separately, and they can easily support separate articles. I've been trying to teach myself complexity theory, and I've found it very confusing to keep track of the different ideas in all of these. I think that having separate articles is going to be more helpful. Does that sound like a reasonable division of topics? -- [[User:Creidieki|Creidieki]] 17:18, 4 April 2006 (UTC)
| |||