Elementary Complexity Theory 205



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