Class Notes
(783,538)

Canada
(480,727)

University of Waterloo
(17,978)

Computer Science
(765)

CS 341
(26)

Forbes Burkowski
(15)

Lecture

#
lecture #9 - NP Completeness
lecture #9 - NP Completeness

lecture #9 - NP Completeness

Unlock Document

University of Waterloo

Computer Science

CS 341

Forbes Burkowski

Fall

Description

NP Completeness
Traveling Salesperson Problem (TSP):
Given a weighted undirected graph G = (V, E), find a cycle
containing every vertex exactly once such that the sum of
weights of edges in the cycle is a minimum.
A greedy algorithm does not work (see next slide).
An exhaustive search will work but takes much too long for
even moderate values of n.
Exhaustivesearch: Trying each permutation of the cities involves
testing (n - 1)! sequences.
There is no known polynomial time algorithm that is
guaranteed to find the minimal cost tour.
There are many polynomial time algorithms to generate
approximations to the optimal solution.
TSP & Greedy (Near Neighbour)
Consider NN solution for rd100 taken from
TSPLIB:
Start here
TSPLIB:http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
1 Practical vs. Impractical
A simple characterization of algorithms:
We will consider polynomial time algorithms to be
practical or efficient
(even with large exponents)
Algorithms that require exponential time (or worse)
are regarded as impractical.
The Question of Efficiency
What do we do if we have a problem like TSP
that has no polynomial time solution?
If we could prove that no polynomial time algorithm
can be designed to solve the problem,
then we could go about looking for approximate
solutions or heuristics with knowing that no practical
algorithm exists to find the optimal solution.
There is a set (class) of problems thatquire
exponential solutions and this can be proven.
But there are many other problems (e.g. TSP) for
which such a proof is not known despite
considerable effort by researchers.
2 So instead we must go for a lesser prize:
We prove that the problem is NP-hard.
That is: it is essentially equivalent to other problems for
which no known polynomial time solution exists.
Such a proof does not show that a polynomial time
solution does not exist but only that thousands of other
experts have never found an efficient solution either.
Why is this important?
If you have an NP-hard problem you have two choices:
1.You can decide that all the experts have missed some
vital point and so you set about looking for a polynomial
time solution
2.You decide that you are not likely to do better than the
experts and set about looking for an approximation or
heuristic algorithm that gives a reasonable solution.
Optimization vs. Decision Problems
Optimization problems:
Find a value, object or configuration that optimizes
some function.
For example: in TSP we are looking for a least cost tour.
Decision problems:
The solution of a decision problem is yes or no.
Some examples:
Is a given number a prime number?
In the TSP-D problem we are given a value B and we
want to know whether there is a tour with length < B.
NP-completeness theory deals with decision
problems.
D for Decision
3 Observation:
If the cost function is easy to evaluate, then the
decision problem can be no harder than the
corresponding optimization problem.
For example: If we can find the minimum length of a
TSP tour, then we can compare it to value B and thus
solve the decision problem.
Often the reverse is also true:
If we can solve the decision problem in polynomial time
then we can solve the optimization problem in
polynomial time as well.
Class P (Polynomial)
Review:
What does running time mean?
The running time of an algorithm A is a functAon T (n)
where n is the size of the input instance.
T (n) = worst case time to solve an instance of size n.
A
What is the size of an instance?
Size = number of bits needed to encode the problem
instance.
Definition:
A decision problem Q belongs to the class of
problems P if and only if there exists a polynomial
time algorithm solving problem Q.
4

More
Less
Related notes for CS 341