Content deleted Content added
→New structure?: new section |
→New structure?: response |
||
Line 224:
How should we re-organise this article? Should we divide it (more explicitly) in two parts: (1) computational complexity of ''problems'' and (2) analysis of ''algorithms''? — [[User:Miym|Miym]] ([[User talk:Miym|talk]]) 23:56, 5 June 2009 (UTC)
:To my knowledge, computational complexity theory has (almost) nothing to do with algorithm design and analysis.
:'''Computational complexity''' focusses on classifying computational problems into classes according to shared aspects of their computational complexity. In doing that, the objects of study are mostly these classes of problems (complexity classes), rather than specific problems. Often also some aspects of particular problems are studied, such as [[graph isomorphism]], the [[SAT]] problem, or [[SL|undirected st-connectivity]].
:For the running time of concrete computational problems, complexity theory often provides a very coarse answer: For instance, the [[2-satisfiability]] problem is [[NL-complete]] and can thus be solved in time <math>O(n^c)</math> for some fixed number ''c''. The algorithm witnessing such a bound is often rather straightforward and would be considered trivial or even worthless from the viewpoint of algorithm design. Computational complexity ''does not care about the concrete value'' of the number ''c''. The message of this is a structural one: Although the [[2-satisfiability]] problem, a problem in logic, looks different from the [[ST-connectivity]] problem in graph theory, its internal structure is extremely similar to the latter. Indeed, <em>all</em> NL-complete problems are mutually extremely similar in structure.
:'''Algorithm design''' and '''analysis of algorithms''' focuses on providing efficient solutions to computational problems. Algorithm design almost always focuses on a particular problem; and running time analysis of algorithms is even more special: it is devoted to understanding a particular solution to a particular computational problem.
:For concrete computational problems, Algorithm design often has a very detailed answer: On a [[random access machine]], the [[2-satisfiability]] problem can be solved in time O(n) via breadth-first search. On a [[Turing machine]] (a different machine model), the resource requirements of this algorithm would be analyzed again, possibly leading to a different result, maybe <math>O(n^2)</math>. In algorithm design, we have to agree on a machine model, whereas the results from complexity theory are independent of the machine model.
:There are small overlaps between the two fields. Most notably, the existence of a particular polynomial-time algorithm for the SAT problem would be a solution to the P versus NP problem. But, whereas already an algorithm running in time <math>O(2^\sqrt{n})</math> on a random access machine would undoubtedly be considered as a breakthrough in algorithm design, it would not have any immediate consequence for computational complexity theory. In my personal experience, this viewpoint appears to be shared by most complexity theorists and algorithm research folks. 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]). Further evidence is given by the following: The [http://facweb.cs.depaul.edu/jrogers/complexity/ call for papers] of the conference on computational complexity does nowhere contain the words "algorithm", "running time" or so. Compare with the topics of the [[European Symposium on Algorithms]], a major conference on design and analysis of algorithms. There almost none of topics has to do with computational complexity.
:Therefore, I find it necessary to have a separate article devoted to algorithm design, and to take out most of the material on algorithm design. To avoid confusion from its very origins, I also advocate to reserve the word ''complexity'' to the complexity of computational ''problems'', and to use ''running time'' or ''resource consumption'' when talking about ''algorithms'', but this would be a topic for another day. Beware that I have provided multiple reliable sources to back up this opinion. Please, if you have a different standpoint, justify your claims. [[User:Hermel|Hermel]] ([[User talk:Hermel|talk]]) 13:01, 15 June 2009 (UTC)
| |||