Appendix B: Elementary Complexity Theory

First, we need to deļ¬ne some basic concepts. An algorithm is a well-deļ¬ned

computational procedure which takes a variable input and halts with an output.

An algorithm is called deterministic if it follows the same sequence of operations

each time it is executed with the same input. A randomized algorithm is one

that makes random decisions at certain points in the execution, so the execution

paths may diļ¬er each time the algorithm is invoked with the same input.

The amount of time required for the execution of an algorithm on a computer

is measured in terms of bit operations, which are deļ¬ned as follows: addition,

subtraction, or multiplication of two binary digits; the division of a two-bit

integer by a one-bit integer; or the shifting of a binary digit by one position.

The number of bit operations to perform an algorithm is called its computational

complexity or simply its complexity. This method of estimating the amount of

time taken to execute a calculation does not take into account such things as

memory access or time to execute an instruction. However, these executions

are very fast compared with a large number of bit operations, so we can safely

ignore them. These comments are made more precise by the introduction of the

following notation.

Deļ¬nition B.1 (Asymptotic or Big O Notation) Suppose that f and g are

positive real-valued functions. If there exists a positive real number c such that

f (x) < cg(x) (B.2)

for all suļ¬ciently large x, then we writeB.1

f (x) = O(g(x)) or simply f = O(g). (B.3)

(In the literature f << g is also often used to denote f = O(g).)

The asymptotic notation Big O is the order of magnitude of the complexity,

an upper bound on the number of bit operations required for execution of an

algorithm in the worst-case scenario, namely, the largest running timeB.2 of all

inputs of a particular length. The greatest merit of this method for estimating

execution time is that it is machine-independent. In other words, it does not rely

upon the speciļ¬cs of a given computer, so the order of magnitude complexity

remains the same, irrespective of the computer being used.

suļ¬ciently large means that there exists some bound B ā R+ such that f (x) < cg(x)

B.1 Here

for all x > B. We just may not know the value of B explicitly. Often f is deļ¬ned on N rather

than R, and occasionally over a subset of R.

B.2 The running time is deļ¬ned as the number of bit operations executed for a given input.

Hence, asymptotic running time is deļ¬ned as the measure of how the running time of an

algorithm increases as the size of the input increases without bound. The term expected

running time is an upper bound on the running time for each input (with expectation in the

probability sense taken over all inputs of the random number generator used by the algorithm),

expressed as a function of the input size (see Remark 1.13 on page 8).

Ā© 2003 by CRC Press LLC

206 Appendix B

Example B.4 A simple example to illustrate the asymptotic notation is given

by f (n) = 12n21 +21n17 +Ļn5 +12nā’1, wherein we ignore all lower terms except

n21 and even ignore the coeļ¬cient 12 since f = O(n21 ), given that the highest

order term dominates the other terms on large inputs, and O(cf ) = O(f ) for any

constant c. The above can be generalized as follows. If f (n) = O(nm ) + O(nk )

where m ā„ k, then f (n) = O(nm ). When dealing with logarithms, this has an

application as follows. Since we have the identity logb (n) = ln(n)/ ln(b) for any

base b with ln(n) = loge (n) for the natural base e, then O(logb (n)) = O(ln(n))

for any such base b since the constants, as we have seen, are irrelevant in the

asymptotic notation. Also, the amount of time taken by a computer to perform

a task is (essentially) proportionalB.3 to the number of bit operations. In the

simplest possible terms, the constant of proportionality, which we deļ¬ne as the

number of nanosecondsB.4 per bit operation, depends upon the computer being

used. This accounts for the machine-independence of the asymptotic method of

estimating complexity since the constant of proportionality is of no consequence

in the determination of Big O.

A fundamental time estimate in executing an algorithm is polynomial time

(or simply polynomial); that is, an algorithm is polynomial when its complexity

is O(nc ) for some constant c ā R+ , where n is the bitlength of the input to the

algorithm, and c is independent of n. (As we observed in Example B.4, any

polynomial of degree c is O(nc ).) In general, these are the desirable algorithms,

since they are the fastest. Therefore, roughly speaking, the polynomial-time

algorithms are the good or eļ¬cient algorithms. For instance, the algorithm is

constant if c = 0; if c = 1, it is linear; if c = 2, it is quadratic, and so on.

Examples of polynomial time algorithms are those for the ordinary arithmetic

operations of addition, subtraction, multiplication, and division. On the other

hand, those algorithms with complexity O(cf (n) ) where c > 1 is constant and f

is a polynomial on n ā N are exponential time algorithms or simply exponential.

A subexponential time algorithm is one for which the complexity for input n ā N

is

Ln (r, c) = O(exp((c + o(1))(ln n)r (ln ln n)1ā’r ) (B.5)

where r ā R with 0 ā¤ r < 1 and c is a positive a constant (see Footnote 5.2 for a

deļ¬nition of o(1)). Subexponential time algorithms are faster than exponential

time algorithms but slower than polynomial time algorithms. (Note that the

case which is the case r = 0 in (B.5) is polynomial in ln n.) For instance, it

can be shown that the DLP discussed on page 39 is Lp (1/3, c) where p is the

prime modulus under consideration. Exponential time algorithms are, again

roughly speaking, the ineļ¬cient algorithms. ā instance, the method of trial-

For

division as a test for primality of n ā N uses n steps to prove that n is prime,

if indeed it is. If we take the maximum bitlength N = log2 n as input, then

ā

n = 2(log2 n)/2 = 2N/2 , which is exponential. Algorithms with complexity

B.3 To say that a is proportional to b means that a/b = c, a constant, called the constant of

proportionality. This relationship is often written as a ā b in the literature.

B.4 A nanosecond is 1/109 of a second ā” a billionth of a second.

Ā© 2003 by CRC Press LLC

Elementary Complexity Theory 207

O(cf (n) ) where c is constant and f (n) is more than constant but less than

linear are called superpolynomial. It is generally accepted that modern-day

cryptanalytic techniques for breaking known ciphers are of superpolynomial time

complexity, but nobody has been able to prove that polynomial time algorithms

for cryptanalyzing ciphers do not exist.

The following table gives some illustrations of time complexity analysis of

algorithms in terms of what we might call a āreal-world scenarioā.

Suppose that the unit of time on the computer at our disposal is a microsec-

ond (a millionth (1/106 ) of a second), and assume an input of n = 106 bits.

Then the following gives us some time complexities for various values.

complexity of algorithm time to execute number of bit ops.

106

one second

O(n)

11.5741 = 1012 /(106 Ā· 24 Ā· 3600) days

O(n2 ) 1012

31, 709 = 1018 /(106 Ā· 24 Ā· 3600 Ā· 365) years

O(n3 ) 1018

O(cf (n) ) longer than the known life of the universe

Complexity theory also divides problems into classes based upon the algo-

rithms required to solve them. To understand this type of complexity, we need

to deļ¬ne some basic notions. Letā™s start with the notion of a problem which

means a general question to be answered, deļ¬ned by a description of its pa-

rameters (sometimes called free variables) and the properties the answer, called

a solution, is required to satisfy. If the parameters are speciļ¬ed, this is called

an instance of the problem. A decision problem is one whose solution is āyesā

or ānoā. A problem is called intractable if no polynomial time algorithm could

possibly solve it, whereas one can be solved by a polynomial time algorithm is

called tractable. (See Remark 1.9 on page 7 on unsolvable, computationally easy

and computationally infeasible problem. Also, see Footnote B.9.)

Now we need the notion of a TuringB.5 machine, which is a ļ¬nite state

machine having an inļ¬nite read-write tape, i.e., our theoretical computer has

inļ¬nite memory and the ability to search for and retrieve any data from memory.

B.5 Alan Mathison Turing (1912ā“1954) was born on June 23, 1912 in Paddington, London,

England. By 1933 Turing had already read Russell and Whiteheadā™s Principia Mathematica

and was deeply immersed in the study of logic. By 1938, he had received his Ph.D. under

Alonzo Church at Princeton for a thesis entitled Systems of Logic Based on Ordinals. He

later returned to England and worked in the British Foreign Oļ¬ce, where he got involved in

cryptanalyzing the German Enigma cryptosystem. Toward this end, he invented a machine

called the BOMBE which was operational on March 18, 1939. In August 1939, the British

government seconded the Code and Cypher School to Bletchley Park, a Victorian country

mansion in Buckinghamshire, halfway between Oxford and Cambridge. From 1939 to 1942,

the researchers at Bletchley Park, including Turing, were cryptanalyzing U-boat Enigma cryp-

tograms, helping to win the battle for the Atlantic. In 1945, he began work at the National

Physical Laboratory in London, where he helped to design the Automatic Computing Engine,

which led the world at the time as a design for a modern computer. In 1948, Turing became

the deputy director of the Computing Laboratory at Manchester, where the ļ¬rst running ex-

ample of a computer using electronically stored programs was being built. His contributions

include pioneering eļ¬orts in artiļ¬cial intelligence. In 1950, he wrote a paper on machine in-

telligence, presenting what has come to be known as the Turing test. By 1951, he had been

elected as Fellow of the Royal Society. In 1952, he was arrested for violation of the British

homosexuality statutes. His death from potassium cyanide poisoning occurred while he was

doing experiments in electrolysis. It is uncertain whether this was an accident or deliberate.

Ā© 2003 by CRC Press LLC

208 Appendix B

More speciļ¬cally, a (deterministic, one-tape) Turing Machine has an in-

ļ¬nitely long magnetic tape (as its unlimited memory) on which instructions

can be written and erased. It also has a processor that carries out the instruc-

tions: (1) move the tape right, (2) move the tape left, (3) change the state of the

register based upon its current value and a value on the tape, and write or erase

on the tape. The Turing Machine runs until it reaches a desired state causing it

to halt. A famous problem in theoretical computer science is to determine when

a Turing Machine will halt for a given set of input and rules. This is called the

Halting Problem. Turing proved that this problem is undecidable, meaning that

there does not exist any algorithm whatsoever for solving it. The Church-Turing

Thesis (which came out of the 1936 papers of Turing and Church)B.6 essentially

says that the Turing Machine as a model of computation is equivalent to any

other model for computation. (Here we may think of a āmodelā naively as

a simpliļ¬ed mathematical description of a computer system.) Therefore, Tur-

ing Machines are realistic models for simulating the running of algorithms, and

they provide a powerful computational model. However, a Turing Machine is

not meant to be a practical design for any actual machine, but is a suļ¬ciently

simple model to allow us to prove theorems about its computational capabilities

while at the same time being suļ¬ciently complex to include any digital com-

puter irrespective of implementation. (See [223] for the Church-Turing thesis,

and for a more number-theoretic approach see [245].)

Complexity theory designates a decision problem to be in class P if it can be

solved in polynomial time, whereas a decision problem is said to be in class NP

if it can be solved in polynomial time on a nondeterministic Turing Machine,

which is a variant of the normal Turing Machine in that it guesses solutions to a

given problem and checks its guess in polynomial time. Another way to look at

the class NP is to think of these problems as those for which the correctness of

a guess at an answer to a question can be proven in polynomial time. Another

equivalent way to deļ¬ne the class NP is the class of those problems for which a

āyesā answer can be veriļ¬ed in polynomial time using some extra information,

called a certiļ¬cate (see Chapter 7). For instance, the problem of answering

whether or not a given n ā N is composite is a problem in NP since, we can

verify in polynomial time if it is composite given the certiļ¬cate of a nontrivial

divisor a of n. However, it is not known if this problem is in P. See [156].

The class P is a subset of the class NP since a problem that can be solved in

polynomial time on a deterministic machine can also be solved, by eliminating

the guessing stage, on a nondeterministic Turing Machine. It is an open problem

in complexity theory to resolve whether or not P = NP. However, virtually

everyone believes that they are unequal. It is generally held that most modern

B.6 Alonzo Church (1903ā“1995) was born June 14, 1903 in Washington, D.C. He held a posi-

tion as a professor of mathematics at Princeton from 1929 to 1967. Then he went to UCLA

to join the faculty as a professor of mathematics and philosophy. Among his many achieve-

ments is the 1936 result, called Churchā™s Theorem, which says that arithmetic is undecidable.

His interests involved not only mathematical logic, but also recursion theory and theoretical

computer science. He is certainly regarded as one of the greatest logicians of the twentieth

century. He died Friday, August 11, 1995 in Hudson, Ohio.

Ā© 2003 by CRC Press LLC

Elementary Complexity Theory 209

ciphers can be cryptanalyzed in nondeterministic polynomial time. However, in

practice it is the deterministic polynomial-time algorithm that is the end-goal

of modern-day cryptanalysis. Deļ¬ning what it means to be a ācomputationally

hardā problem is a hard problem. One may say that problems in P are easy, and

those not in P are considered to be hard (for instance, see [198, pp. 195ā“196].)

However, there are problems that are regarded as computationally easy, yet are

not known to be in P. For instance, the Miller-Rabin-Selfridge Test, which we is

studied in Section 4.4, is such a problem. It is in the class RP, called randomized

polynomial time or probabilistic polynomial time. Here, P ā RP ā NP. A

practical (but mathematically less satisfying) way to deļ¬ne āhardā problems is

to view them as those which have continued to resist solutions after a concerted

attack by competent investigators for a long time up to the present.

Another classiļ¬cation in complexity theory is the NP-complete problem,

which is a problem in the class NP that can be proved to be as diļ¬cult as any

problem in the class. Should an NP-complete problem be discovered to have a

deterministic polynomial time algorithm for its solution, this would prove that

NP ā P, so P = NP. Hence, we are in the position that there is no proof that

there are any hard problems in this sense, namely, those in NP but not in P.

Nevertheless, this has not prevented the ļ¬‚ourishing of research in complexity

theory. The classical NP-complete problem is the Travelling Salesman Problem:

A travelling salesman wants to visit n ā N cities. Given the distances between

them, and a bound B, does there exist a tour of all the cities having total length

B or less? The next in the hierarchy of complexity classiļ¬cation is EXPTIME,

problems that can be solved in exponential time.

Thus far, we have been concerned with the time it takes for an algorithm

to execute, measured (asymptotically ā” the worst-case scenario) in terms of

the number of bit operations required. Another component of complexity is the

amount of computer memory (storage required) for the computation of a given

algorithm, called the space requirement. Time calculation on a Turing Machine

is measured in terms of the number of steps taken before it enters a halt state,

as we have discussed above. The space used is deļ¬ned as the number of tape

squares visited by the read-write head (where we think of the tape as having

inļ¬nitely many squares read, written or erased by a āread-write headā). Thus,

the notion of polynomial space takes on meaning, and since the number of steps

in a computation is at least as large as the number of tape squares visited, then

any problem solvable in polynomial time is solvable in polynomial space. Thus,

we deļ¬ne PSPACE as those problems that can be solved in polynomial space,

but not necessarily in polynomial time. Hence, PSPACE-complete problems

are those such that if any one of them is in NP, then PSPACE=NP, and

if any one of them is in P, then PSPACE=P. At the top of the hierarchy

of the classiļ¬cation of problems in terms of complexity is EXPSPACE, those

problems solvable in exponential space, but not necessarily in exponential time.

It is known that P=EXPTIME and NPāPSPACE=EXPSPACE. (There

are also the nondeterministic versions, NPSPACE and NEXPSPACE that

we will not discuss here (see [94]).) The following provides an illustration of the

above discussion on the hierarchy of problems in complexity theory.

Ā© 2003 by CRC Press LLC

210 Appendix B

Figure 9.5: Hierarchy of Problems in Complexity Theory

ā¤ā ā

ā˜

ā— ā”

ā

EXPSPACE EXPTIME PSPACE-complete PSPACE NP-complete NP P

ā’ ā‘

ā– ā•

ā ā™

ā£ ā¢

There are other types of complexity such as circuit complexity, which looks at the

connection between Boolean circuits and Turing Machines as a computational

model for studying P vis-`-vis NP and aļ¬liated problems. We will not discuss

a

these more advanced themes here (see [223] for deeper considerations).

Roughly speaking, complexity theory can be subdivided into two categories:

(a) structural complexity theory, and (b) the design and analysis of algorithms.

Essentially, category (a) is concerned with lower bounds, and category (b) deals

with upper bounds. Basically, the primary goal of structural complexity theory

is to classify problems into classes determined by their intrinsic computational

diļ¬culty. In other words, how much computing time (and resources) does it

take to solve a given problem? As we have seen, the fundamental question in

structural complexity theory remains unanswered, namely, does P = NP? We

have been primarily concerned with the analysis of algorithms, which is of the

most practical importance to cryptography.

The foundations of complexity theory were laid by the work done starting in

the 1930s by Turing and Church, among others (see Footnote B.5). As we have

seen in this appendix, the ļ¬rst goal was to formalize the notion of a computer (or

realistic model thereof such as the Turing Machine). Then the goal was whether

such devices could solve various mathematical problems. One of the outcomes

of this research, again as we have seen, is that there are problems that cannot

be solved by a computer. This was contrary to the program set out by David

Hilbert in 1900, which sought to show that all mathematical problems could

be answered in a deterministic fashion. For example, Hilbertā™s tenth problem

was to ļ¬nd an algorithm for testing whether a polynomial has an integral root.

The Church-Turing thesis, discussed above, provides the precise deļ¬nition of an

algorithm necessary to resolve Hilbertā™s tenth problem. In 1970, MatiyasevichB.7

B.7 Yuri Matiyasevich was born March 2, 1947 in Leningrad, the USSR, and is currently a

Russian citizen. He obtained his Doctor of Sciences in Physics and Mathematics at the Steklov

Institute of Mathematics, Moscow in 1972 (approved by the Higher Attestation Committee

in 1973). He became a professor at St. Petersburg State University in 1995, was awarded a

Docteur honoris Causa by the University of Auvergne, France in 1996, and became a Corre-

spondent Member of the Russian Academy of Sciences in 1997. Among his other honours are

the A.A. Markov Prize in Mathematics from the Academy of Sciences of the USSR in 1980;

a Humboldt Research Award in 1997; and the Paciļ¬c Institute of Mathematical Sciences

Distinguished Chair held in 1999ā“2000. He is currently head of the Laboratory of Mathe-

matical Logic at the St. Petersburg Department of the Steklov Institute of Mathematics (see:

Ā© 2003 by CRC Press LLC

Elementary Complexity Theory 211

proved that there does not exist an algorithm for testing whether a polynomial

has integral roots. Hence, Hilbertā™s tacit assumption, that an algorithm existed

and merely had to be found, was ļ¬‚awed. In fact, the Church-Turing thesis may

be considered to be the cement between informal and formal deļ¬nitions of an

algorithm.

It may be argued that one of the pinnacles of complexity theory is the above

classiļ¬cation of problems according to computational diļ¬culty. In cryptog-

raphy, the primary goal is to establish cryptosystems that are computationally

easy (to use), whereas all algorithms for cryptanalysis are computationally hard.

The establishment of complexity theory may be credited to the pioneering

work of Stephen Cook,B.8 Richard Karp,B.9 Donald Knuth,B.10 and Michael

Rabin.B.11 Each of these individuals has since been awarded the highest honour

in computer science research ā” the Turing Award.

http://www.pdmi.ras.ru/). He has more than sixty publications and one book Hilbertā™s Tenth

Problem ļ¬rst published in 1993.

B.8 Stephen Cook (1939ā“) was born in Buļ¬alo, New York. In 1966, he received his Ph.D.

from Harvard after which he spent four years as an Assistant Professor at the University of

California, Berkeley (UC Berkeley). In 1970, he was appointed Associate Professor to the

Department of Computer Science at the University of Toronto. By 1975, he had attained

full professorship and by 1985 the rank of University Professor. In 1982, he won the Turing

award for his work in complexity theory. Among numerous other awards, he has also been

recognized as a Fellow of the Royal Society of Canada.

B.9 Richard M. Karp (1935ā“) received his Ph.D. in Applied Mathematics from Harvard in

1959, after which he joined the IBM Thomas J. Watson Research Center until 1968. From

then until 1994, he held the position of Professor of Computer Science, Mathematics, and

Operations Research at UC Berkeley. From 1994 until June of 1999 (when he returned to

UC Berkeley), he held a position as Professor of Computer Science and Adjunct Professor of

Molecular Biotechnolgy at the University of Washington. His fundamental research activities

are glued together by his interest in combinatorial algorithms. Among his numerous achieve-

ments is the Turing award, received in 1985, for his extensions of Stephen Cookā™s ideas on

NP-completeness. The Cook-Karp thesis says that if a problem is in P, then it is said to

be computationally tractable (feasible), whereas a problem which is not in P is said to be

computationally intractable (infeasible), albeit no proof of this thesis exists.

B.10 Donald Knuth (1938ā“) ļ¬rst saw a computer (an IBM 650) in his freshman year at Case

Institute of Technology (CIT), now called Case Western Reserve, in 1956. He was so fasci-

nated that he stayed up all that night reading the manual on the 650, teaching himself some

fundamentals for programming it, and was able to improve upon the programming techniques

illustrated therein. By 1960, he was graduated from CIT, and in 1963, he achieved his Ph.D.

from the California Institute of Technology (Cal Tech), after which he joined the faculty there

as a professor of mathematics. In 1968, he went to Stanford University and in 1977 was en-

dowed with its ļ¬rst chair in computer science. By 1993, he was Professor Emeritus of (the art

of) Computer Programming. By his own admission, his lifeā™s work is his magnum opus: The

Art of Computer Programming, which he actually started writing in 1966 and which today

has three volumes (of a projected seven volumes, the fourth of which is slated to be out by

2007). Among his numerous recognitions is the Turing award given to him in 1974. He now

lives on the Stanford University campus with his wife and two children.

B.11 Michael Rabin (1931ā“) was born in Breslau, Germany (now Wroclaw, Poland) in 1931.

In 1956, he obtained his Ph.D. from Princeton University where he later taught. In 1958, he

moved to the Hebrew University in Jerusalem. He is known for his seminal work in establishing

a rigorous mathematical foundation for ļ¬nite automata theory. For such achievements, he

was co-recipient of the 1976 Turing award, along with Dana S. Scott, both students of Church

(see Footnote B.6). He now divides his time between positions at Harvard and the Hebrew

University in Jerusalem.

Ā© 2003 by CRC Press LLC