CS341 Lecture Notes - Np-Completeness, Np-Hardness, Polynomial
• 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.
• Exhaustive search: 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
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 that require
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.
• 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
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
• 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 Band we
want to know whether there is a tour with length < B.
–NP-completeness theory deals with decision
problems.D for Decision