A concise introduction to Computer Science

S. E. Venegas-Andraca
Quantum Information Processing Group
Tecnolgico de Monterrey - Escuela de Ciencias e Ingeniera
http://www.mindsofmexico.org/sva
salvador.venegas-andraca@keble.oxon.org
August 2015

Introduction

The Theory of Computation is a scientific field devoted to understanding the

fundamental capabilities and limitations of computers, and it is divided into
three areas:
1. Automata Theory. The study of different models of computation.
2. Computability Theory. This focuses on determining which problems can
be solved by computers and which cannot.
3. Complexity Theory. The objective in this area is to understand what
makes some problems computationally hard and others easy.
The development and analysis of algorithms starts with defining a problem in proper mathematical jargon, followed by choosing a model of computation upon which we first determine whether such a problem is solvable, in
principle, by implementing a series of steps in the model of computation we
have adopted. If that were the case, then the last step would be to quantify
the amount of resources needed to execute the algorithm.
In the following lines we present a very concise introduction to the concepts and ideas in computer science that lead us to consider the use of stochastic and quantum mechanical processes for algorithm development.
This introduction to theoretical computer science is mainly based on [2],
[3], and [1].

Decision problems, encoding schemes and languages

Central to the use of sophisticated mathematical structures and physical

theories in the creation of algorithms is the concept of NP-completeness,
a theory designed to be applied only to decision problems. Let us briefly
review what a decision problem is by using a primus inter pares example:
The Traveling Salesman Problem.
Definition 2.1. The Traveling Salesman Problem (optimization version)
INSTANCE: A finite set C = {c1 , c2 , . . . cm } of cities and a distance
d(ci , cj ) N, the set of natural numbers.
QUESTION: Which is the shortest tour of all the
cities in C, that is,
Pm1
an ordering [c(1) , c(2) , . . . , c(m) ] of C such that [ i=1 d(c(i) , c(i+1) )] +
d(c(m) , c(1) ) is minimum?
Definition 2.2. The Traveling Salesman Problem (decision problem
version)
INSTANCE: A finite set C = {c1 , c2 , . . . cm } of cities a distance d(ci , cj )
N and a bound B N.
QUESTION: Is there a tour of all the cities in C having total length
no more than B, that is, an ordering [c(1) , c(2) , . . . , c(m) ] of C such that
P
[ m1
i=1 d(c(i) , c(i+1) )] + d(c(m) , c(1) ) B?
Notes:
1) The key point to observe about this optimization-decision problems
correspondence is that, so long as the cost function is relatively easy to
evaluate, the decision problem can be no harder than the corresponding optimization problem.
For example, suppose we have an instance of the TSP composed of 10,000
cities all connected (i.e., the system can be represented by a fully connected
undirected graph). If we were able to find the shortest tour of all cities then
we could easily use that minimum cost in order to determine whether it is
possible to satisfy the inequality of the decision-problem version of TSP, for
an arbitrary threshold B. Formally speaking, if we know the shortest tour
of all cities, it suffices to execute a polynomial time algorithm to determine
whether the decision-problem version of TSP can be satisfied or not.
2

2) The reason for the restriction to decision problems is that they have
a very natural formal counterpart, which is a suitable object to study in a
mathematically precise theory of computation. This counterpart is called a
language.
3) A word of caution: The previous words do not mean that optimization
problems are NOT amenable to computer analysis. In fact, optimization
problems are very well placed at the heart of state-of-the-art applications of
computer science. Optimization problems are members of a set known as
NP-Hard problems, a most interesting topic we shall address shortly as soon
as we understand the fundamentals of NP-completeness.
Definition 2.3. Alphabet. 1) Any finite set of symbols is an alphabet.
2) For any alphabet , we denote by the set of all finite strings of symbols
from .
Definition 2.4. Encoding scheme. An encoding scheme e for a problem
provides a way for describing each instance of by an appropriate string
of symbols over some fixed alphabet .
The correspondence between decision problems and languages is brought
about by the encoding schemes we use for specifying problem instances whenever we intend to compute with them.
Thus the problem and the encoding scheme e for partition into
three classes of strings: those that are not encodings for instances of , those
that encode instances of for which the answer is no, and those that encode
instances of for which the answer is yes. This third class of strings is the
language we associate with and e:
Definition 2.5. Language for problem under encoding e.
L(,e)= { x | is the alphabet used by e, and x is the encoding under
e of an instance I Y }
Our formal theory is applied to decision problems by saying that, if a
result holds for the language L(,e) it also holds for the problem
under the encoding scheme e.

Models of computation

So far we have formally defined what a language is, being that a preliminary
step towards the definition of an algorithm. However, before delivering such a
definition, let us make a quick reflection: when we think of an algorithm, i.e.
a set of steps executed in a computer, we are assuming we have a computer,
i.e. a physical machine or a mathematical model upon which we may be able
to execute such steps. Consequently, prior to the definition of an algorithm,
we must define a computer.

3.1

Deterministic vs Nondeterministic models of computation

For every single mathematical model of a computer machine, it is possible

to define two variants: deterministic and nondeterministic versions.
When every step of a computation follows in a unique way from the preceding step we are doing deterministic computation. In a nondeterministic
machine, several choices may exist for the next state at any point. Non determinism is a generalization of determinism.
How does a nondeterministic machine (NM) compute? Suppose that we
are running an NM on input symbol i and come to a qi state with multiple
states to proceed. After reading input symbol i, the machine splits into
multiple copies of itself and follows all the possibilities in parallel. Each copy
of the machine takes one of the possible ways to proceed and continues as
before. If there are subsequent choices, the machine splits again. If the
next input symbol does not appear on any of the arrows exiting the state
occupied by a copy of the machine, that copy of the machine dies, along with
the branch of the computation associated with it.
Another way to think of a nondeterministic computation is as a tree of
possibilities. The root of the tree corresponds to the start of the computation.
Every branching point in the tree corresponds to a point in the computation
at which the machine has multiple choices. The machine accepts if at least
one of the computation branches ends in an accept state. A graphical illustration of a nondeterministic computation is given in Fig. (1).

Deterministic Computation
000
000
111
Start 111
0
1
000
111

1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
00
11
00
11
0
1
00
11
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
00
11
00
11
00
11
0
1
0
1
0
1
0
1
0
1
0
1

..
.1
0

Accept
or
Reject

1
0
0
1
0
1
0
1
00
11
0
1
00
11
00
11
00
11
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
00
11
00
11
00
11

Reject

Nondeterministic Computation
00
11
00
11
00
11
111111
000000
00000000
11111111
0
1
00
11
000000
111111
00000000
11111111
0
1
000000
111111
00000000
011111111
1
000000
111111
00000000
11111111
0
1
000000
111111
00000000
11111111
0
1
000000
111111
00000000
11111111
000
111
000
111
00
11
0
1
000000
111111
000
111
000
111
00
11
000
111
00000000
11111111
0
1
000
111
00
11
00000
11111
0
1
000
111
000
111
00
11
000
111
00000000
11111111
0
1
000
111
00
11
00000
11111
0
1
000
111
00000000
11111111
0
1
000
111
00
11
00000
11111
0
1
000
111
00000000
11111111
0
1
000
111
00
11
00000
11111
0
1
000 1
111
00000000
11111111
0
000
111
00
11
00000
11111
0
1
000
111
00
11
00000000
11111111
0
000
111
00
11
000
111
000
111
00
11
00000
11111
0
1
000 1
111
000
111
00 11
11
00
11
00000000
11111111
00
11
00
000
111
000
111
00
11
000
111
00
11
00
11
00
11
000
111
000
111
00
11
000
111
00 111
11
00
11
00
11
000
111
000
00
11
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
00
11
00
11
Reject
00
11

.
.
.

.
.
.

0
1
0
1
0
1
0
1
111
000
0
1
000
111
000
111
000
111
00 11
11
00
11
00
11
00
00
11
00
11
00
11
00
11
000
111
000
00 111
11
00
11
000
111
000
111
000
000
111
Accept 111
000
111
000
111

.
.
.

Accept

00
11
00
11
00
11
00
11
1111
0000
000
111
0
1
0000
1111
000
111
0
1
0000
1111
000
111
0
1
0000
1111
000
111
0
1
0000
1111
000
0 111
1
0000
1111
000
111
0
1
00
11
000
111
00
11
00
11
000
111
00
00 111
11
000 11
00
11

Figure 1: In deterministic computation, every single step is fully determined by

the previous step. In nondeterministic computation, a step may be followed by n
new steps or, equivalently, a nondeterministic computer machine makes n copies
of itself, one for each possibility.

3.2

Deterministic Turing Machines

A Deterministic Turing Machine (DTM) is an accurate model of a general

purpose computer. A DTM, pictured schematically in Fig. (2), can do
everything a real computer can do (more on this in the following subsection.)
A DTM consists of a scanner and a limitless memory-tape that moves
back and forth past the scanner. The tape is divided into squares. Each
square may be blank (t) or may bear a single symbol (0 or 1, for example).
The scanner is able to examine only one square of tape at a time (the scanned
square). The scanner has mechanisms that enable it to erase the symbol on
the scanned square, and to move the tape to the left or right, one square at
a time. Also, the scanner is able to alter the state of the machine: a device
within the scanner is capable of adopting a number of different states, and
the scanner is able to alter the state of this device whenever necessary. The
operations just described - erase, print, move, and change state - are the
basic operations of a DTM. Complexity of operation is achieved by chaining
together large numbers of these simple basic operations.
5

Finite State Control

ReadWrite Head
00000000000000000000000000000000000000
11111111111111111111111111111111111111
111111
000000
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
11111111111111111111111111111111111111
00000000000000000000000000000000000000
111111
000000
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

...

...

Figure 2: The hardware elements of a Deterministic Turing Machine (DTM)

are a scanner (read-write head plus a finite state control system) and a limitless
memory-tape (the tape is divided into squares or cells). The scanner reads and
writes information on the cells of the tape and controls the state of the DTM.

Definition 3.1. Deterministic Turing Machine. A Deterministic Turing

Machine (DTM) is a 7-tuple M = (Q, , , , q0 , qaccept , qreject ), where Q, ,
are all finite sets and
1. Q is the set of states
2. is the input alphabet not containing the blank symbol t,
3. is the tape alphabet, where t and
4. : Q Q {L, R} is the transition function,
5. q0 Q is the start state,
6. qaccept Q is the accept state, and
7. qreject Q is the reject state, where qaccept 6= qreject .
Definition 3.2. Computation with a Deterministic Turing Machine.
Let M = (Q, , , , q0 , qaccept , qreject ) be a DTM.
Initially M receives its input w on the leftmost n squares of the
tape, and the rest of the tape is filled with blank symbols. The head starts
on the leftmost square of the tape ( does not contain the blank symbol, so
the first blank appearing on the tape marks the end of the input.) Once M
has started, the computation proceeds according to the rules described by .
The computation continues until it enters either the accept or reject states
at which point it halts. If neither occurs, M just does not stop.

As a DTM computes, changes occur in the current state, the current tape
contents, and the current head location. A setting of these three items is
called a configuration of the DTM. A configuration C1 yields configuration
C2 if the Turing machine can legally go from C1 to C2 in a single step. In an
accepting configuration the state of the configuration is qaccept . In a rejecting
configuration the state of the configuration is qreject . Accepting and rejecting
configurations are halting configurations and do not yield further configurations.
A DTM M accepts input w if a sequence of configurations C1 , C2 , . . . Ck
exists, where
1. C1 is the start configuration of M on input w,
2. each Ci yields Ci+1 , and
3. Ck is an accepting configuration.
We say that M accepts language A if A = {w|M accepts w}, i.e. A is
the set of all strings accepted by M .

3.3

Example. Running a program in a Deterministic

Turing Machine

The program specified by = {0, 1, t} (t is the blank symbol), Q =

{q0 , q1 , q2 , q3 , qaccept , qreject } and , provided in Table 1, is used in a deterministic Turing machine M to determine whether a number can be divided
by 4 or, equivalently, whether the last two digits of a binary number, reading
from left to right, are two consecutive zeros.

Table
Q/
q0
q1
q2
q3

1. Example of
0
(q0 , 0, R)
(q2 , t, L)
(qaccept , t, L)
(qreject , t, L)

a deterministic Turing machine.

1
t
(q0 , 1, R)
(q1 , t, L)
(q3 , t, L)
(qreject , t, L)
(qreject , t, L) (qreject , t, L)
(qreject , t, L) (qreject , t, L)

The program works as follows. For a state qi {q0 , q1 , q2 , q3 } specified

in the LHS column and a given alphabet symbol sj {0, 1, t} specified in
the top row, the box that corresponds to row qi and column sj and contains
three symbols: the first symbol is the new state of M , the second symbol is
the new alphabet symbol that will be written in the current cell (substituting
symbol si ) and the third symbol specifies the motion direction of the readwrite head. So, row qi and column sj are the current configuration of M and
the symbols contained in the box corresponding to row qi and column sj are
the next configuration of M .
For example, let X = 10100 be an input binary string (we shall read the
input string from left to right). The initial state of M is q0 and M s tape
reads as t 1 0 1 0 0 t
where our first input symbol (in bold face) is the leftmost 1. So,the initial
configuration of M is q0 , 1.
The transition function specifies that for a state q0 and input symbol 1,
M must take q0 as new state, write the value 1 in the cell where its read-write
head is now located (1) and take its read-write head one cell forward, i.e.
to the right. So, M is now in the configuration q0 , 0 and its tape reads as
t 1 0 1 0 0 t .
The full run
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
Step 6:
Step 7:
Step 8:

of this program is given in the following sequence

q0 , t10100t q0 , t10100t
q0 , t10100t q0 , t10100t
q0 , t10100t q0 , t10100t
q0 , t10100t q0 , t10100t
.
q0 , t10100t q0 , t10100t
q0 , t10100t q1 , t10100t
q1 , t10100t q2 , t1010 t t
q2 , t1010bt qy , t101 t tt

We have said that DTMs can do everything a real computer can do, and
real computers compute values of functions. Transducer Machines, a DTM
variant, are capable of those computations.
Definition 3.3. Transducer Machines. A transducer machine T is used
to compute functions. T has a string w as input and produces another
string y as output. Output y is stored in a special tape called the output
tape. Given a function f , a transducer T computes f if the computation T (w)
reaches a final state containing f (w) as output whenever f (w) is defined (if
f is not defined, T never reaches a final state). A function f is computable
if a Turing Machine T exists capable of computing it.

3.4

The Church-Turing Thesis

Alan Turing published a most influential paper in 1936 [5] in which he pionereed the theory of computation, introducing the famous abstract computing machines now known as Turing Machines.
In [5], Turing:
1) Defined a systematic method, our modern definition of an algorithm.
2) Provided a rigorous definition of a Turing machine, i.e. a powerful model
of computation.
3) Proved that it was possible to build a particularly powerful machine called
Universal Turing Machine (UTM) that could simulate any other Turing
machine in reasonable time.
4) Conjectured the Church-Turing Thesis, in which he established an
equivalence correspondence between the existence of Turing machines and
that of systematic methods. If the Church-Turing thesis is correct, then the
existence or non-existence of systematic methods can be replaced throughout
mathematics by the existence or non-existence of Turing machines.
5) Explained the fundamental principle of the modern computer, the idea
of controlling the machines operation by means of a program of coded instructions stored in the computers memory, i.e. a Turing machine capable
of simulating any other Turing machine (the Universal Turing Machine being
the actual digital computer and the simulated Turing machine the program
that has been encoded in the digital computers memory).
6) Proved that not all precisely stated mathematical problems can be solved
by computing machines (examples: the decision and the halting problems.)
9

No wonder why Alan Turing is such a big name! When Turing wrote
[5], a computer was not a machine at all, but a human being. A computer
was a mathematical assistant who calculated by rote, in accordance with a
systematic method. The method was supplied by an overseer prior to the
calculation. It is in that sense that Turing uses the word computer in [5]
and a Turing machine is an idealized version of this human computer. What
Turing did in [5] was to propose a mathematical formalism for the idealization
of a human computer as well as to study the calculation capabilites and
limitations of that mathematical model.
3.1. The Church-Turing Thesis. Three ways to express the thesis are:
1. The UTM can perform any calculation that any human computer can
carry out.
2. Any systematic method can be carried out by the UTM.
3. Every function which would be naturally regarded as computable can be
computed by the Universal Turing Machine.
It is somewhat ironic, at least for me, that the branch of S&T that is perceived by society at large as a very precise and quantitative discipline, rests
upon a conjecture! This is one of the reasons for the tremendous philosophical
and scientific relevance of David Deutschs formulation of the Church-Turing
principle:
3.2. The Church-Turing principle [6]. Every finitely realizable physical
system can be perfectly simulated by a universal model computing machine
operating by finite means.
In Deutschs words, the rationale behind the Church-Turing priciple was
to reinterpret Turings functions which would be naturally regarded as computable as the functions which may in principle be computed by a real physical system. For it would surely be hard to regard a function naturally as
computable if it could not be computed in Nature, and conversely.

10

3.5

Algorithmic Complexity for DTMs

The performance of models of computation in the execution of an algorithm

is a fundamental topic in the theory of computation. Since the quantification
of resources (in our case, we focus on time) needed to find a solution to a
problem is usually a complex process, we just estimate it. To do so, we
use a form of estimation called Asymptotic Analysis in which we are
interested in the maximum number of steps Sm that an algorithm must be
run on large inputs. We do so by considering only the highest order term
of the expression that quantifies Sm . For example, the function F (n) =
18n6 + 8n5 3n4 + 4n2 has five terms, and the highest order term is 18n6 .
Since we disregard constant factors, we then say that f is asymptotically at
most n6 . The following definition formalises this idea.
Definition 3.4. Big O Notation. Let f, g : N R+ . We say that f (n) =
O(g(n)) if , no N such that n no
f (n) g(n)
So, g(n) is an asymptotic upper bound for f (n) (f is of the order of g).
Bounds of the form n , > 0 are called polynomial bounds, and bounds

of the form 2n , R+ are called exponential bounds. f (n) = O(g(n))

means informally that f grows as g or slower. Big O notation says that one
function is asymptotically no more than another.
Example 1. Prove the following statements:
P
1) Pni=1 i = O(n2 )
2) Pni=1 i2 = O(n3 )
3) ni=1 3i = O(3n )
Example 2. A warm-up:
1) Linear complexity
2) Quadratic complexity

11

A DTM can be used to find a solution to a problem, so how efficiently

such solution can be found? As stated previously, we shall be interested in
finding the fastest algorithms. Let us now introduce a few concepts needed
to quantify the efficiency of an algorithm.
The time complexity of an algorithm A expresses its time requirements
by giving, for each input length, the largest amount of time needed by A to
solve a problem instance of that size.
Definition 3.5. Time Complexity Function for a DTM. Let M be a
DTM. We define f : N N as the time complexity function of M , where
f (n) is the maximum number of steps that M uses on any input of
length n.
Definition 3.6. Time Complexity Class for DTMs. Let t : N R+
be a function. We define the time complexity class TIME(t(n)), as the
collection of all languages that are decidable by an O(t(n)) time DTM.
Definition 3.7. Class P. The class of languages that are decidable in polynomial time on a deterministic
single-tape Turing machine is denoted by P
S
and is defined as P = k TIME(nk ) As an example, the language provided
in subsection (3.3) is in P.
A most important question to reflect on:
1. What is the relationship between the algorithmic complexities introduced
in example 2 and the formal definition of complexity in DTMs? In other
words, what is the meaning of elementary step in both a Turing machine
and an algorithm?
The central idea here is: for each algorithmic elementary step one has
to perform a polynomial number of steps in a DTM.
Example:
- Computational complexity of an algorithm that computes the multiplication of two matrices of order n by using the textbook definition. Executing
this algorithm under the rational of a DTM would be living hell!

12

A polynomial time or tractable algorithm is defined to be one whose time

complexity function is O(p(n)) for some polynomial function p, where n is
used to denote the input length. Any algorithm whose time complexity
function cannot be so bounded is called an exponential time or intractable
algorithm. Tractable algorithms are considered as acceptable, as a sign that
a satisfactory solution for a problem has been found. Finding a tractable
algorithm is usually the result of obtaining a deep mathematical insight into
a problem. In contrast, intractable algorithms are usually solutions obtained
by exhaustion, the so called brute-force method, and are not considered satisfactory solutions.
Example of tractable and ingenious algorithms.
- Computational complexity of an algorithm that computes the multiplication of two matrices of order n by using the textbook definition. O(n3 ).
- Strassens algorithm for matrix multiplication. O(nlog2 7 )
Example of intractable algorithms, i.e. intractable problems.
- Computational complexity of 3SAT (formal definition in pages 18-19 of
this document). If n binary variables 2n different n-bit strings!
- Computational complexity for TSP. Factorial complexity.

So, no tractable algorithm for the Traveling Salesman Problem (2.1) is

known so far. All solutions proposed so far are based on enumerating all possible solutions. Why is the Traveling Salesman problem intractable?
Nobody knows for sure. It could be either that we need a deeper knowledge
of the characteristics of this problem or, simply, that the Traveling Salesman
problem is inherently intractable. However, no proof for neither of these two
alternatives has been supplied so far.

13

3.6

Nondeterministic Turing Machines (NTMs)

It is indeed possible to define a nondeterministic version of a Turing machine.

If interested in the formal definition of such a computational beast, you may
want to look at my DPhil thesis (http://mindsofmexico.org/sva/vitae.html)
as well as to the references provided therein.
For the sake of this discussion, I just want to say that it is possible to prove
that deterministic Turing machines and nondeterministic Turing machines
are equivalent in computational power, i.e. any problem a deterministic
Turing machine can solve, can also be solved by a nondeterministic Turing
machine. However, this computational equivalence does not mean that both
models of computation spend the same amount of resources for solving the
same problems, as we shall see in the following section.

3.7

Algorithmic Complexity for NTMs

We start by offering the definitions of time complexity function and time

complexity class for NTMs.
Definition 3.8. Time Complexity Function for an NTM. Let MN be
an NTM. We define g : N N as the time complexity function of MN , where
g(n) is the maximum number of steps that MN uses on any branch of its
computation on any input length n.
Definition 3.9. Time Complexity Class for NTMs. Let t : N R+
be a function. We define the time complexity class NTIME(t(n)), as the
collection of all languages that are decidable by an O(t(n)) time nondeterministic Turing machine.

14

For an NTM to accept string w it is enough to find just one branch b

in its computation tree that accepts w. However, a practical problem
with this definition is to find b as an NTM can have an infinite
(or exponentially big) number of different branches. Therefore, a
more operational method for doing nondeterministic computation
is needed. An important discovery in the theory of computation is the fact
that the complexities of many problems are linked by means of a concept
closely related to the definition of NP problems: verifiability.

3.8

Verifiability and NP problems

Let us suppose we have a proposed solution for the Traveling Salesman problem (2.2). In this case, we could easily check whether such a proposal is
indeed a solution, all we need is a DTM that verifies whether the proposed
solution is right or not.
Definition 3.10. Verifier. A verifier for a language A is an algorithm V ,
where A = {w|V accepts (w, c) for some string c}.
We measure the time of a verifier only in terms of the length of w, so a
polynomial time verifier runs in polynomial time in the length of w. A
language A is polynomially verifiable if it has a polynomial time verifier.
The string c, a certificate, is additional information needed by the verifier.
Note that a fundamental difference between an NTM and a verifier is that
an NTM finds solutions, while a verifier only checks whether a proposal is a
solution or not.
We now proceed to define a most important class of languages in Computer Science:
Definition 3.11. Class NP. The class of languages that have polynomial
time verifiers is known as NP.
What is the relation between the abstract model of an NTM and the
concepts of verifiers and NP languages class? The answer is given in Theorem
(1) and its proof can be found in [2].
Theorem 1. A language is in NP if and only if it is decided by a nondeterministic polynomial time Turing machine.

15

P = NP and NP-complete problems

?

The problem P = NP is a fundamental topic in the theory of computation.

It is known that P NP as any polynomial language can be checked with
a polynomial verifier. Also, it can be proved [3] that
Theorem 2. If a problem NP then a polynomial p such that can be
solved by a deterministic algorithm having time complexity O(2p(n) ).
Therefore,
1) NP problems can all be solved by algorithms that have exponential
functions as upper bounds. However, such exponential upper bounds are not
necessarily minimum upper bounds.
2) We are sure that some NP problems (those that are also P) are also
solved by algorithms that have polynomial functions as upper bounds. In
some cases (i.e. for some problems), we know whether those polynomial
upper bounds are optimal.
3) Due to theorem (2) there is a widespread belief that P 6= NP although
?
no proof has been delivered and therefore P = NP remains an open problem.

NP-completeness

OK, we are getting closer to the kind of problems for which we need both
stochastic processes and quantum mechanics to tackle them. The key idea
to understand NP-completeness is that of polynomial transformation.
Definition 5.1. A polynomial transformation from a language L1 1 to
a language L2 2 is a function f : 1 2 that satisfies the following two
conditions:
1) There is a polynomial time DTM that computes f
2) x 1 , x L1 f (x) L2
If there is a polynomial transformation from L1 to L2 , we write L1 L2
and read L1 transforms to L2 .
If 1 and 2 are decision problems, with associated encoding schemes e1
and e2 , we shall write 1 2 (with respect to the given encoding schemes)
whenever there exists a polynomial transformation from L[1 , e1 ] to L[2 , e2 ].
16

Now, the following lemma and definition will provide the grounds for
defining classes of problems.
Lemma 1. If L1 L2 and L2 L3 L1 L3 .
Definition 5.2. Polynomially equivalent languages. Two languages
L1 and L2 (two decision problems 1 and 2 ) are polynomially equivalent
whenever L1 L2 and L2 L1 (both 1 2 and 2 1 )
Together, polynomial equivalence and the previous lemma build an equivalence relation. The class P forms the equivalence class of the computationally easiest problems. NP-complete problems, jewels of the crown, also
conform a class. Let us formally define these lovely beasts.
Definition 5.3. NP-Complete Languages and Problems. A language
L is NP-complete if
1) L NP, i.e. L has a polynomial time verifier or, equivalently, whether
L is decidable in polynomial time by a nondeterministic Turing machine, and
2) For all other languages Li NP Li L, i.e. Li NP a polynomial
transformation from Li to L.
Due to our capacity to go from problem instances to languages by means
of encoding schemes, we can also say that a decision problem is NPcomplete if NP and, for all other decision problems i NP we find
that i .
The following theorem could be the key, for any of us, not only to get
1106 USD in the pocket (http://www.claymath.org/millennium/), but also
to immortality, like The Beatles of Computer Science :)
Theorem 3. If B is NP-complete and B P , i.e. B = O(p(n)) for some
polynomial p(n) P = NP.
Now, when I learned Complexity Theory, I found a bit difficult (and tiresome) to imagine how to prove, in practice, the membership of a problem A
to the NP-complete sphere, because that proof requires to build a polynomial
transformation which takes an arbitrary NP problem and converts it into A.
Fortunately for us computer scientists, there is an easier way to make this
proof:
17

Theorem 4. If L1 and L2 belong to NP, L1 is NP-complete and L1 L2

L2 is NP-complete.
Proof. L1 is NP-complete, i.e. a polynomial transformation f such that
Li NP Li L1 .
Moreover, there is another polynomial transformation g from L1 to L2 as,
by hypothesis, L1 L2 .
Therefore Li L1 and L1 L2 Li L2 , Li NP, and, since L2 is
a member of NP, we conclude that L2 is NP-complete.

5.1

SAT

The first NP-complete problem (chronologically speaking) is the Satisfiability problem, also known as SAT problem. This membership was proved
by Stephen Cook ([7]). Let us now define SAT as well as several variants of
SAT that are also members of the NP-complete set.
Definition 5.4. Boolean formula. A Boolean formula is an expression
involving Boolean variables and operations. For example: = (xy)(
x z)
A Boolean formula is satisfiable iff some assignments of 0s and 1s to the
variables, makes the formula evaluate to 1.
Definition 5.5. SAT problem. The satisfiability problem is to test whether
a Boolean formula is satisfiable, i.e.
SAT = {| is a satisfiable formula}
All propositional forms, i.e. well formed Boolean formulae (that is to
say, Boolean formulae generated by a formal language), can be expressed
in Conjunctive Normal Form (CNF), i.e. in a conjunction of clauses, where
each clause is a disjunction of literals:
^_
P = ( xj )i
i

Thus, it is possible to express the SAT problem in CNF:

Definition 5.6. Satisfiability. Instance: A set U of variables and a conjunction of clauses C over U .
Question: Is there a satyisfying truth assignment for C?
18

Theorem 5. [7] SAT is NP-complete

Due to Theorem (5), the SAT problem is a key element in the theory of
computation. Let us remark that in the above definitions of SAT problem
there is no constraint neither in the number of clauses nor in the number
of literals per clause. Thus, in order to make SAT amenable to algorithmic
analysis we define a variation with a limited number of literals per clause:
Definition 5.7. The K-SAT Problem. Let S = {x1 , x2 , . . . , xn } be a set
of Boolean variables and C be a collection of clauses over SVwhere
Wk each clause
has k literals, i.e. C is a conjunction of disjunctions C = i [( j=1 xj )].
INSTANCE: A set S of variables and a collection of clauses over S.
QUESTION: Is there a satisfying truth assignment for C?
Examples of NP-completeness.
- 3SAT is NP-complete (polynomial transformation from KSAT to 3SAT).
- A more difficult proof: KSAT is NP-complete (polynomial transformation
from any NP problem to KSAT).

References
[1] S.E. Venegas-Andraca, DPhil thesis: Discrete Quantum Walks and
Quantum Image Processing, CQC, University of Oxford (2006)
[2] M. Sipser, Introduction to the Theory of Computation, PWS (2005).
[3] M.R. Garey and D.S. Johnson, Computers and Intractability. A Guide
to the Theory of NP-Completeness, W.H. Freeman and Co., NY (1979).
[4] R. Motwani and P. Raghavan, Randomized Algorithms, CUP (1995).
[5] A.M. Turing, On Computable Numbers, with an application to the
Entscheidung problem, Proceedings of the London Mathematical Society, 42, pp. 230-265 (1936-37).
[6] D. Deutsch, Quantum theory, the church-turing principle and the
universal quantum computer, Proc. Royal Soc. of London. Series A,
400(1818), pp. 97117 (1985).
[7] S.A. Cook, The Complexity of Theorem-Proving Procedures, Proc. 3rd
Ann. ACM Symposium on the Theory of Computing, pp. 151-158 (1971).
19