Complexity Theory
Complexity Theory
(Reference: Chapter 6 of Maheshwari & Smid)
University of New Brunswick
CS2333: Computability and Formal Languages
1 Complexity Theory
Complexity Theory
Introduction
I We have talked about:
I problems that we can solve with finite automata,
I problems that we can solve with pushdown automata,
I problems that we can solve with Turing machines (and
therefore with what we normally think of as computers),
I and problems that can never be solved with any computer /
by any algorithm.
I The idea in this last part of the course is to talk about the
fact that, even if a problem is solvable in theory, the required
algorithm might take way too long for it to be useful in
practice.
2 Complexity Theory
Complexity Theory
Time Complexity
I With time complexity analysis, we are interested in talking
about how long it will take for an algorithm to run.
I This can be extremely useful when it comes to determining
which of two algorithms would be more efficient for a
particular task, or which of two data structures would be the
better choice in a given situation.
I We are interested in analyzing this in a way that does not
depend on the amount of memory we have, the processor(s)
we are using, etc.
I We focus on the number of steps that an algorithm takes
when run with an input of a particular size.
3 Complexity Theory
Complexity Theory
Worst-case running time
I Definition: Let M be a deterministic TM that halts on all
inputs.
The worst-case running time of M is a function f : N → N,
where f (n) is the maximum number of steps that M will use
on any input of length n.
I We say that:
I M runs in time f (n).
I M is an f (n) time Turing machine.
I Also of interest sometimes: average-case running time
analysis
4 Complexity Theory
Complexity Theory
Example
I Consider a TM that will check if a given input string
w ∈ {0, 1}∗ is of the form 0m for some integer m ≥ 0.
I Given an input string w , of length n, how many steps would
the TM require in the worst case?
I For each of the n characters, if the character is not 0, then
reject the input. Otherwise, move to the next character.
I If we reach the blank at the end of the string without rejecting
the string, then accept it.
I Total number of steps (in the worst case): n + 1
5 Complexity Theory
Complexity Theory
Asymptotic analysis
I Often, counting the exact number of steps (e.g.,
6n3 + 2n2 + n + 30) is a significant amount of work and not
absolutely necessary.
I We care more about things like:
I If we double the size of the input, does the algorithm take
twice as long? four times as long? eight times as long? etc.
I This is what asymptotic analysis (commonly called big-O
analysis) allows us to do.
6 Complexity Theory
Complexity Theory
Asymptotic analysis
I Informal idea:
I We are interested in what happens to the running time of an
algorithm as the input size n gets larger and larger.
I As n grows, the highest-order term dominates and we can
basically ignore everything else.
I For example, in the expression 6n3 + 2n2 + n + 30, if
n = 10000, then the 2n2 + n + 30 becomes almost
insignificant compared to the 6n3 .
I As n grows, we care less and less about constants. For
example, as n increases, the 6 in 6n3 becomes less and less
important. The n3 is what really matters.
I So we say that something with running time 6n3 + 2n2 + n + 30
has an asymptotic running time of O(n3 ) [big-O of n3 ]
7 Complexity Theory
Complexity Theory
Formal definition
I Let f and g be functions f : N → N, g : N → N. We say that
f (n) ∈ O(g (n)) if ∃ positive integers c and n0 such that
∀n ≥ n0 , f (n) ≤ c · g (n).
I We say that g (n) is an asymptotic upper bound for f (n).
I What does this really mean?
I It means that, as n gets large (≥ some value n0 ), f (n) is
guaranteed to be no more than some constant multiple of g (n).
The function g (n) is an asymptotic upper bound for f (n).
8 Complexity Theory
Complexity Theory
Polynomial running times
I In other courses, you will see more on techniques for proving
that one function is a bound for another, and about how to
analyze running times.
I For this course, just know that big-O analysis exists and that
an algorithm can be described as being O(n), O(n2 ),
O(n log n), etc.
I Note: A bound of the form nk for some k > 0 is called a
polynomial bound. Something like 2n or 3n is an
exponential bound.
9 Complexity Theory
Complexity Theory
Polynomial running times
I Big picture of how running times relate to each other: on the
board
I Note that if a running time is in O(n2 ), then it is also in
O(n3 ), O(n4 ), etc. Normally, we are interested in the lowest
upper bound we can find.
10 Complexity Theory
Complexity Theory
Running time and nondeterminism
I Definition: Let M be a nondeterministic TM that decides
some language L.
The running time of M is the function f : N → N, where f (n)
is the maximum number of steps that M takes on any branch
of its computation on any input of length n.
I One way to think of this: If we guess an exact sequence of
steps to follow, and then follow that sequence, what is the
longest that it could take?
11 Complexity Theory
Complexity Theory
More on polynomial time
I As mentioned before, any algorithm that has a running time of
O(nk ) for some k > 0 is called a polynomial-time algorithm.
I In practice, algorithms with polynomial running time are
considered to be tractable: realistically solvable by a
computer in a reasonable amount of time.
I Exponential-time algorithms (e.g., O(2n )) are intractable.
12 Complexity Theory
Complexity Theory
More on polynomial time
I Note: A running time of n100 is polynomial, but wouldn’t
really be practical. However, algorithms with running times of
n100 don’t really happen naturally. If an algorithm is
polynomial, it is typically O(n4 ) or better.
I The distinction of polynomial vs. not polynomial has proven to
be useful.
I Examples on the board showing the difference between
polynomial-time and exponential-time algorithms
13 Complexity Theory
Complexity Theory
Polynomial equivalence
I Note: All reasonable deterministic computational models are
polynomially equivalent.
I Anything that can be done on one model can be done on
another model with at most a polynomial increase in running
time.
I For example, maybe something can be done in O(n) steps on a
multi-tape TM, but requires O(n2 ) steps on a single-tape TM.
I Question: Is this also true for deterministic and
non-deterministic Turing machines?
14 Complexity Theory
Complexity Theory
The class P
I Definition: P is the class of languages that are decidable in
polynomial time on a deterministic Turing machine.
(Roughly speaking, P corresponds to the set of all problems
that can be solved realistically on a computer.)
I Examples of problems in P:
I Given a string x, is x ∈ {0k 1k | k ≥ 0}?
I Given a CFG G and a string w , is w ∈ L(G )?
15 Complexity Theory
Complexity Theory
The class P
I Some problems are decidable, but are not in P. No
polynomial-time deterministic algorithm exists to solve them.
I Some problems are decidable, but nobody knows if they are
in P or not.
16 Complexity Theory
Complexity Theory
The class N P
I Definition: N P is the class of languages that can be decided
in polynomial time by a nondeterministic Turing machine.
I Some problems are known to be in N P, but it is not known if
they are in P.
I One of the big open problems in computer science and
mathematics is:
Is P = N P?
I Nobody knows! Most researchers believe that P =
6 N P, but
nobody has been able to prove it yet.
17 Complexity Theory
Complexity Theory
N P-completeness
I There is a class of problems called N P-complete problems
(e.g., the Hamiltonian path problem).
I Every N P-complete problem X has the following properties:
I X ∈ NP
I If problem X can be shown to be in P, then it would follow
that every problem in N P is in P.
18 Complexity Theory
Complexity Theory
N P-completeness
I This has huge implications:
I If anyone can find a polynomial-time, deterministic algorithm
for even one of these problems, then P = N P. This would
mean that a large class of problems currently believed to be
computationally intractable would suddenly become tractable.
I Since people have been trying very hard for years to solve some
of these problems efficiently, then it is almost certain that
P= 6 N P.
19 Complexity Theory