Talk:Computational complexity theory

From Wikipedia, the free encyclopedia

You have new messages (last change).
Former featured article Computational complexity theory is a former featured article. Please see the links under Article Milestones below for its original nomination page (for older articles, check the nomination archive) and why it was removed.
This article is within the scope of WikiProject Computer science.
??? This article has not yet received a rating on the assessment scale.
??? This article has not yet received an importance rating on the assessment scale.

Contents

[edit] older entries

I wonder where would be a good place to mention that we know some problems not in P, for instance Presburger arithmetic. --AxelBoldt

I've added it to Complexity classes P and NP. It should also be added to EXPTIME, whenever someone gets around to writing it. I would put it under P too, except that's more of a redirect than a real article. --LC

I've added a note explaining (in brief) what the Co classes are. What do you think about trying to consolidate many of these articles? For example, NP and Co-NP should probably be the same article, as should NP-complete and Co-NP-complete

GulDan 18:10, 31 Jul 2003 (UTC)

[edit] Suggestions for real-life examples

There are several problems that seem to have a high computational complexity, but are not yet fully computerized. One example is payroll processing. The computational complexity of payroll processing is made unnecessarily high by various tax laws. Splitting such taxes as social security between the employer and employee is economically pointless and serves only to increase the complexity of payroll processing. (These taxes really ought to be paid by the employees so that they have a more honest conceptual understanding of the full tax burden they bear. Besides, payroll processing is taxing enough without having to pay payroll taxes.) Various state income tax schemes further complicate the process, as do laws such as the Davis-Bacon Act that require the payment of different wages for different jobs.

Another example is the computation of efficient paths of transport for freight and passengers. The highway transportation system solves this problem by parallelizing the computation among the various drivers. Other situations such as ports, shipping and receiving departments, airports, and train depots often have more centralized control that results in an extremely high concentration of computational complexity and the need for great speed in real time. Hence the high security often employed in such situations and the need to avoid distracting workers such as longshoremen from their jobs. Perhaps these situations would benefit from the further study of computational complexity theory.

[edit] Featured article removal

This article was removed from being a featured article with the following comments that may be helpful in improving the article: [1]

How on Earth did this get featured? No mention of models of computation. No mention of Turing machines! No explanation of non-determinism. Nothing about randomized algorithms. Nothing about parallel computation and the structure of P. Nothing about reduction. No pictures. No history. Gdr 08:40, 2004 Jul 26 (UTC)

  • Support removal. The weird thing is that I don't even see this article on Wikipedia:Featured article candidates/Featured log. When the WP:FA page was new, a lot of people added articles themselves, as the candidate process was kind of unclear. - DropDeadGorgias (talk) 17:02, Jul 26, 2004 (UTC)
  • Support removal; this is nowhere near comprehensive. — Matt 17:32, 27 Jul 2004 (UTC)
  • Remove posthaste. The "notable researchers" section is particularly disturbing; you can hardly do such a list justice, certainly not with only a dozen names. +sj+ 05:10, 11 Aug 2004 (UTC)

[edit] "Invitation" to work on questionable off-topic article

Work is currently in progress on a page entitled Views of Creationists and mainstream scientists compared. Also currently being worked upon is Wikipedia: NPOV (Comparison of views in science) giving guidelines for this type of page. It is meant to be a set of guidelines for NPOV in this setting. People knowledgable in many areas of science and the philosophy of science are greatly needed here. And all are needed to ensure the guidelines correctly represent NPOV in this setting.  :) Barnaby dawson 21:12, 29 Dec 2004 (UTC)

We don't need a plethora of articles detailing everybody's views on this highly controversial topic. Wikipedia is an encyclopedia, not a platform for expressing various distorted politico-quasi-religious pseudoscientific views. For further information on creationism, the reader is referred to the Bible. There is an article on so-called intelligent design, which already pushes the limits of what is acceptable on Wikipedia, although the "concept" does seem to be widely reported in the mass media. And what on earth has this got to do with computational complexity theory? -- 130.94.162.61 15:17, 24 December 2005 (UTC)
This is clearly moot now. Barnaby dawson 17:52, 24 December 2005 (UTC)

[edit] Merge notices

Notices were added requesting a merge from DSPACE and DTIME. I have expanded both of those articles significantly, and believe they should stand alone as articles. Since there were no rationales given for the merge, I have removed the merge notices; I would of course be happy to discuss this further if someone would still like to consider a merge. -- Creidieki 21:56, 2 April 2006 (UTC)

Not sure how I forgot to discuss it here, but here goes. IMO the two concepts DTIME and DSPACE are too similar to themselves and to this article, and there isn't a lot said about them not already said (or should be said) in this article. The author of these articles agree with me (see his talk page).

BTW, I'm not entirely sure on the procuedure, but aren't merge notices supposed to be discussed before removed?

Ripper234 15:39, 3 April 2006 (UTC)

The correct procedure is to change them to {{mergedisputed}}. While considering myself a bit of a mergist, I'm inclinded to say that keeping them seperate may be preferable over merging. First of all I think it would be nice to see all complexity classes in Category:Complexity classes, and not miss a few due to being combined with this article. Secondly I think there is some room for expansion of DSPACE and DTIME. Thirdly, I hope this article will once be a good introductory article, I feel that an larger treatment of several complexity classes might hinder this. Of course, I'm always open to counter-arguments. Cheers, —Ruud 16:27, 3 April 2006 (UTC)
I'm sorry if I didn't follow procedure; I hadn't been able to find any discussion on the proposed merge. I agree that the two complexity measures (not classes) DTIME and DSPACE are similar to each other, and that they're very important entities to complexity theory. I do think that they deserve separate articles, because I think that there's enough to say about them to require that, and that there are plenty of articles that should link to DTIME and DSPACE separately from complexity theory (for example, P) is a certain amount of deterministic time, and should mention so. I'll try to expand those articles and make the distinctions a little more clear today. -- Creidieki 17:14, 3 April 2006 (UTC)
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). 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 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? -- Creidieki 17:18, 4 April 2006 (UTC)
Accepted. I removed the merge notices. Ripper234 05:55, 7 April 2006 (UTC)

[edit] Translate German WP article?

It seems that this article would benefit considerably from material contained in the German WP article. 213.3.104.34 07:58, 5 April 2006 (UTC)

  • If you can convince someone to provide a translation, I would be happy to incorporate the material into the English article. Unfortunately, I do not speak German. -- Creidieki 19:29, 5 April 2006 (UTC)
While I know we generally frown upon automated translation services, this link[2] will translate the German page fairly well. Because of the way the links are set up, if you click on a wikilink, you will be sent to a translated version of the target page. --Carl (talk|contribs) 03:57, 15 September 2006 (UTC)

[edit] Good Article nomination has failed

The Good article nomination for Computational complexity theory has failed, for the following reason(s):

I think the reasons that led the article from losing FA status (which it probably should never have had in the first place) are still reasons not to give the article GA status. I know most people don't read german but if you look at the german page you can still see a much more elaborate structure, pictures and so on. The current article fails the GA criteria in a number of ways: slightly narrow focus, certainly less than "compelling prose", not enough references and so on. As someone who works in the field, there are also a number of things in the article that make me cringe like "The most important complete set is NP-complete." Well, so fix it I guess... but in the meantime it's way too early to give the article GA status. Pascal.Tesson 03:34, 11 July 2006 (UTC)

[edit] Fixing this up

I am working on re-writing at least parts of this article. I understand computational complexity theory well, though I am by far not an expert on it, so my knowledge of some specific areas are lacking. Feel free to help out, intervene or to give suggestions.--Konst.able 09:00, 9 October 2006 (UTC)

I changed the introduction to be less technical and contain more applications to the "real world". I think this is more to the proposed standard. Some of the replaced material better belongs in the sections to which it pertains. I'll contribute more as I find time. Scottcraig 18:03, 17 October 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../c/o/m/Talk%7EComputational_complexity_theory_1425.html"