Content deleted Content added
→List of complexity theorists: new section |
|||
Line 255:
Kolmogorov Complexity (length of generating program for given data), rather than run time, is what many if not most people would mean by 'Computational Complexity', and this article should refer to it early on with a reference to its Wikipedia article. Other than that, I'm not sure that the material covered in the article is actually a 'subject' per se. P = NP is a legitimate subject: so are algorithmic design, cryptography, etc. The mere design of a notation about how long something takes to run, isn't much of a subject. The little o and big O notations, for instance, have many other uses in math unrelated to algorithm runnning time: I hope they have a separate article. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/63.229.11.118|63.229.11.118]] ([[User talk:63.229.11.118|talk]]) 04:55, 18 June 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:I strongly disagree. As I said a few lines above: Compare the recent books by Arora and Safra: "Computational Complexity: A Modern Approach" ([http://www.cs.princeton.edu/theory/index.php/Compbook/Draft draft available online]) and by Goldreich: "Computational Complexity: A conceptual perspective" ([http://www.wisdom.weizmann.ac.il/~oded/cc-book.html drafts of some chapters available online]). It IS indeed a subject on its own, and is as such different from Kolmogorov complexity. [[User:Hermel|Hermel]] ([[User talk:Hermel|talk]]) 18:19, 21 June 2009 (UTC)
== List of complexity theorists ==
I removed this text from the article:
{{Prose|1=paragraph|date=August 2009}}
<blockquote>
The field was subsequently expanded by many researchers, including:
<--
This is NOT a "Hall of Fame". All people with wikipedia articles are notable.
Please add only names which are described as "groundlayers" by the peers,
with citations and summary of major contributions
-->
* [[Manuel Blum]]
* [[Allan Borodin]]
* [[Stephen Cook]]
* [[Michael Fellows]]
* [[Michael R. Garey]]
* [[Oded Goldreich]]
* [[Juris Hartmanis]]
* [[David S. Johnson]]
* [[Richard Karp]]
* [[Marek Karpinski]]
* [[Donald Knuth]]
* [[Leonid Levin]]
* [[Christos H. Papadimitriou]]
* [[Alexander Razborov]]
* [[Richard Stearns (computer scientist)|Richard Stearns]]
* [[Leslie Valiant]]
* [[Andrew Yao]]
</blockquote>
We need to establish some criteria for inclusion, or not have such a list at all. I haven't seen such lists on other articles either. The article on [[physics]] doesn't have a list of notable physicists like Newton, Einstein, etc. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 18:26, 14 October 2009 (UTC)
| |||