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)
:Yes, I also disagree that "many or most people" would think computational complexity is Kolmogorov complexity. --[[User:P3d0|P3d0]] ([[User talk:P3d0|talk]]) 20:00, 14 October 2009 (UTC)
== List of complexity theorists ==
| |||