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([log10(n)] + 1)

in total. It is convenient to say succinctly that the time complexity

of addition is

O(log10(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.