Discrete Mathematics for Computer Science

Complexity of Programs 311

Stephen Cook proved that if propositional satisfiability is in 7), then AfP ___ P. In fact,

Cook proved a stronger result-that satisfiability is A/P-complete-but we shall not even

define that notion here.

5.3.6 Variants on the Definition of Complexity

This material is included primarily to make you aware that there are many variants on

the complexity analysis we have done. We will list several variants here. Some give finer

measures for circumstances when the simplifying assumptions of our previous model are

too extreme. Others measure other important properties of algorithms.

Variant 1: Ways to Measure Input Data Size

We measured the size of the input by counting the number of input values. So, a very

long number counts the same as a very short number. For sorting algorithms, and for

many other algorithms, this is a reasonable simplifying assumption. Even so, for many

algorithms, it is highly unrealistic to count a one-digit number the same as a 1000-digit

number. A common measure is the number of characters it takes to represent the data. So,

for numbers, one can count digits-base 2 or base 10. For character strings, one can count

the number of characters.

For example, code-breaking programs may take only a single integer as data, but the

code breaking takes longer and longer as the numbers get larger. There may be no theo-

retical maximum at all on the number of key operations performed. There is only a finite

number of n-digit numbers, however, so as long as the program always terminates, there is

a maximum on the number of key operations that can be performed on any input from that

finite set.

With this measurement, counting just the number of input data, as we did for sort-

ing algorithms, would be viewed only as a useful approximation of the number of input

characters.

Yet another measure of the size of the input is simply the numbers themselves.

Variant 2: Choices of Key Operations

We have already noted the importance of choosing realistic key operations. We assumed

that each basic operation, such as comparison, addition, subtraction, multiplication, or

division, takes 0(1) time. For most programs, this is a reasonable assumption. However,

suppose we had to multiply arbitrarily large integers accurately. Ordinary long multiplica-

tion of two six-digit numbers takes 36 multiplications of one-digit numbers, as shown in

Figure 5.8.

111111

111111

111111

111111

111111

111111

111111

111111

12345654321

Figure 5.8 Multiplying six-digit numbers.