Lance's dividing-line between "algorithms" and "computational complexity" disagrees with a passage of text I wrote for one of the pages of my research group, in which I said:

*This kind of analysis belongs to two closely-related research fields: algorithmics, the design of algorithms with provable performance guarantees, and computational complexity, the classification of problems according to the kinds of algorithms that can solve them.*According to what I wrote, an NP-completeness result is a work of computational complexity, albeit not usually a very interesting one.

I would not be that interested in getting into a debate about where exactly to draw this dividing-line. But I tend to prefer my own definition, mainly because it defines computational complexity in terms of what it is, rather than what it isn't. The other problem with Lance's definition is that one can imagine some Grand Inquisitor of Computational Complexity, managing to exile all sorts of results from the hallowed halls of computational complexity to the chilly uplands of algorithms, on the grounds that they are often tainted with algorithmic content. Take for example Savitch's Theorem, and its corollary that nondetermistic polynomial space is equivalent to deterministic polynomial space. The proof uses the reachability method, which is clearly an algorithm.

## No comments:

Post a Comment