Content deleted Content added
m Signing comment by 63.229.11.118 - "Requested xref to Kolmogorov complexity, pointed out that the reason the article wanders is that what it's talking about isn't really a well-defined 'subject', per se." |
re: Kolmogorov complexity |
||
Line 241:
== Needs some kind of note/cross-reference to Kolmogorov Complexity, and other remarks ==
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)
| |||