Talk:Computational complexity theory
 | 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. | |||||||||||||||
| ||||||||||||||||
| Current status: Former featured article | ||||||||||||||||
 | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
| |||||||||||||||||||||
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)
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.
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)
"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)
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)
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)
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)
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)
Fixing this up again
I noticed this article in the "pages needing attention" section of the Computer Science project page. I understand that it's already undergone one major rewrite (which I will look over in detail when I have some time) but I have some thoughts off the top of my head that I'd like to share:
- Shouldn't this article be called "Run-time complexity theory"?
- In the opening graf, "scalability" is used to describe algorithm complexity. While this is perhaps an apt analogy, isn't it technically inaccurate to equate the two concepts? "The capacity to handle increasing workloads/throughput" isn't quite the same thing as "the increase in running time as input size increases".
- The Big-O function is mentioned in passing. Small-O, Omega and Theta are not mentioned at all. Neither are the concepts of monotonically increasing functions or asymptotic limits. Shouldn't these concepts be central to the article?
- I didn't notice any discussion of why theoretical run-time complexity classes are superior to empirical measurements or benchmarks. When I learned run-time complexity, a "classic" example we were given right off the bat was a side-by-side comparison of running times for two machines running two different sorting algorithms. Machine A was the equivalent of a 1980's TRS-80, running an O(n lg n) sort. Machine B was a state-of-the-art (at the time) Pentium 4 running an O(n3) sort. For small sizes of n, Machine B was light-years faster, but as the size of n increased, Machine A eventually came to pwn Machine B. I'd like to see a chart like that in the article.
I'll give the page a thorough read and make more detailed suggestions later. Groupthink 13:16, 26 June 2007 (UTC)
Run-time complexity
On second thought, run-time complexity really deserves its own article, and the thrust of this article should remain P- and NP-completeness. Thoughts? Groupthink 02:04, 27 June 2007 (UTC)
- I've added a run-time analysis article. Groupthink 21:02, 28 June 2007 (UTC)
- I disagree. There is already a P/NP page elsewhere. And the majority of complexity theory deals with run-time complexity. P/NP is only included here because of its fundamental importance in complexity theory and computer science in general. If anything, the P/NP could be toned down, and the reader directed to the other page. But thanks for working on this. It could really help from your input. Scottcraig 17:13, 30 June 2007 (UTC)
- Then perhaps computational complexity theory should be merged into run-time analysis, and the material on boolean decidability and P/NP-completeness in comp. complexity should be merged into Boolean satisfiability problem and Complexity classes P and NP respectively? Groupthink 21:42, 30 June 2007 (UTC)
Asymptotic complexity
Currently, asymptotic complexity redirects here. This seems wrong to me - it ought to redirect to a page more like big O notation that actually explains the concept of asymptotic complexity in a much more specific setting. But I'm not sure just where to point it to. What do you think? Dcoetzee 03:53, 7 July 2007 (UTC)
Notable Researchers
This section of the article has been rubbing me the wrong way since the first time I saw this article. I don't see it's relevance, I don't believe that it fits in with Wikipedia's WP:LIST guideline, and the criteria for inclusion of a researcher in that list is uncertain (for one: why is Turing not on the list?) Perhaps it is time to split it out into a new article (List of researches in computational complexity theory) or remove it altogether, leaving only the most vital people relevant to the field (such as Cook, Turing and Knuth) in the See also section.--Konstable 11:05, 7 July 2007 (UTC)
Question about super-exponential growth
I was wondering something, just out of curiosity. (I apologize if this is an in appropriate use of this talk page.) I was reading about hyperbolic growth, and I was wondering if any algorithm has been discovered whose run time grows hyperbolically. In other words, the runtime would be something like , where b is a positive integer, and n is the length of the input. This would mean that, when n=b, the problem requires an "infinite" number of steps, and is therefore undecidable. But for n < b, the problem would be decidable in a finite number of steps. Actually, now that I think about it, this is an inappropriate use of big-O notation, because big-O notation, in complexity theory, is defined in terms of limits at infinity. But still, are there any problems that are decidable for small inputs, but undecidable for sufficiently large inputs? User:Navigatr85 21:33, 7 July 2007 (UTC)
- Here's the problem with trying to define something as – your Big-O upper-bound has to be monotonically increasing beyond a certain point where n > n0. If you argue that n0 is less than b, then you get a big old discontinuity when n = b and your function no longer has the required ordering property. If you argue that n0 is greater than b, then you have a valid ordering property, but negative run-times, which would be undefined.
- However, not every algorithm is boundable with a Big-O limit (see run-time analysis), and there are undecidable algorithms (see halting problem). Unfortunately, I do not know if there are algorithms that are decidable for small inputs but undecidable for large inputs – but I can tell you that there are algorithms whose run-times grow extraordinarily rapidly as n increases, such that the fastest supercomputers in existence would take until the end of the universe to solve problems for sufficiently large inputs (see Ackermann function and busy beaver for examples). See intractability for more info. Groupthink 00:03, 8 July 2007 (UTC)