Talk:Computational complexity theory
 | Computer science Unassessed | ||||||||||||||||
| |||||||||||||||||
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)