8 1 A Taste of Things to Come two digits, compute the carry, if necessary, and add it to the next position. All that requires at most 3 operations, making it 3([log 10 (n)] + 1) in total. It is convenient to say succinctly that the time complexity of addition is O(log 10 (n)). Notice further that a change of the basis of the logarithm amounts to multiplication of its value by a constant hence we can use any basis (actually, computer scientists prefer base 2, since everything is done in binary numbers) and just write O(log n). Similarly, the multiplication of two integers has time complex- ity at most O(log2 n), or quadratic time complexity, while the mul- tiplication of two n × n matrices with integer entries, each smaller than m, requires at most O(n3 log2 m) operations. I do not consider here various interesting and useful ways to speed up the standard procedures see the classical book by Knuth [372] for a very com- prehensive survey of the huge body of knowledge on fast practical algorithms. Why is the class P of polynomial time algorithms so important? From a practical point of view, many known polynomial time al- gorithms cannot be used on modern computers now or in the near future, since the constant in O( ), or the power of the polynomial involved, may be too big for the computation to be completed in any feasible amount of time. As frequently happens in mathematics, P is being studied be- cause it is robust. The actual degree d in the bound O(nd) for complexity depends on data structures and other computer science tricks used but if an algorithm can be implemented as polynomial time one way, it remains polynomial time in all reasonable imple- mentations, and this allows us to work at the theoretical level and ignore the details. Also, there is a school of thought holding that the existence of a polynomial time algorithm should normally suggest the existence of a good and practically feasible polynomial time algorithm. This is how Neal Koblitz (one of the founders of algebraic cryptography) put it in [373, p. 37]: The experience has been that if a problem of practical inter- est is in P, then there is an algorithm for it whose running time is bounded by a small power of the input length. Koblitz’s statement is a metamathematical thesis describing a big class of especially nice algorithms.5 In the next section, I will try to describe even nicer algorithms—but, unfortunately, these are less versatile and less applicable than polynomial time algorithms.
Previous Page Next Page