UTPA STEM/CBI Courses/Data Structures and Algorithms/NP-Completeness

Course Title: Data Structures and Algorithms

Lecture Topic: NP-Completeness

Instructor: Robert Schweller

Institution: University of Texas Pan American

Backwards Design

Course Objectives

• Primary Objectives- By the next class period students will be able to:
  • Know the definitions of the class P, NP, NP-C
  • Be able to identify well know problems in NP-C and P.
  • Be able to prove a given problem is in NP.
  • Be familiar with some well know reductions to prove membership in NP-C.
  • Be able to show a new problem is in NP-C by describing a polynomial time reduction from a known NP-problem.

• Sub Objectives- The objectives will require that students be able to:
  • Read and understand technical definitions. The complexity classes dealt with in this lesson offer a chance for students to appreciate how subtle points in mathematical definitions are important. Students will gain an increased critical and analytical eye for technical details which is of fundamental importance for most areas in science and math.
  • Communicate/describe/write technical mathematical proofs. The subtleties in proofs related to this topic offer a chance to make students aware of any vagueness or lack of clarity in their solutions.

• Difficulties- Students may have difficulty:
  • Understanding the definitions of NP and NP-C.
  • Understanding polynomial time reduction proofs.

• Real-World Contexts- There are many ways that students can use this material in the real-world. Examples are:
  • A number of practical problems exist in the real world that are NP-C problems. Identifying these problems is important as this implies that obtaining an exact solution to the problem in general is intractable, and thus alternate approaches must be used.
  • If even a single NP-C problem where shown to be in P, all problems in NP would be in P, which would have far reaching impacts. Further, if even a single NP-C problem where shown to not be in P, then no NP-C problem could be in P.

Model of Knowledge

• Concept Map
  • Definitions of complexity classes P, NP, NP-C
  • Proving membership in NP
  • Polynomial time reductions to show membership in NP-C

• Content Priorities
  • Enduring Understanding
    • The implications of a problem being in NP-C
    • Knowledge of which class some common problems (3-SAT, 2-SAT, Hamiltonian Path) belong in.
• Important to Do and Know
  • Be able to identify the complexity class of new problems.
• Worth Being Familiar with
  • The class Co-NP.
  • Approximation algorithms

Assessment of Learning

• Formative Assessment
  • In Class (groups)
    • Provide new problem in class. Ask students to show the problem is in NP, then show it is in NP-C or P.
  • Homework (individual)
    • Ask students to show a given problem is in NP, then show it is in NP-C or P.

• Summative Assessment
  • Big mean exam questions.

Legacy Cycle

OBJECTIVE

By the next class period students will be able to:

• Show that a given problem is NP.
• Define the classes P, NP, NP-C.
• Describe how the class P, NP, NP-C are related (what sets are subsets of others, what sets are disjoint).
• Be able to provide a polynomial time reduction from a known NP-hard problem to show NP-hardness of a new problem.

The objectives will require that students be able to:

• Understand how to solve an NP problem.

THE CHALLENGE You've taken a part time job as a software engineer for a sushi delivery company. Your boss is going to fire you unless you can design a program that will compute the shortest possible route to deliver sushi to 1000 different houses. Your mission: Don't get fired.

GENERATE IDEAS

• Students should brainstorm for any solutions to this problem. This should be very open ended.
  • Each group of students should obtain at least one provably correct (but inefficient) solution to the problem.
  • Students should build upon this initial solution in multiple ways:
    • Students should design techniques to speed up their solution while maintaining correctness. The speedup may only be for restricted cases of the problem. Students should prepare arguments for why their solution yields a speedup and in what scenarios.
    • Students may alternately achieve speedups by achieving only close to optimal solutions. Students should be encouraged to argue why the solution obtained is always or likely to be a good approximation, what the speedup achieved is, and whether or not the speedup applies to the general case.
  • If students are unable to efficiently solve the problem, they should discuss other approaches to not get fired, such as convincing the boss that the requested task is not a feasible one.
    • Students should discuss how to argue that the problem is not solvable by an algorithm that is both efficient and accurate.

MULTIPLE PERSPECTIVES

• From the group discussions, groups share with class
  • Each group presents their best strategy to avoid getting fired.
  • Each presented strategy is debated by the entire class. Any holes in the group's argument or analysis should be uncovered and debated.
  • The best solutions should be selected from the different groups.
• Can the boss be convinced that this is a stupid request?
• Introduce a known NP-Complete problem. Discuss the intuitive notation and implications of NP-Completeness.
• Introduce formal definitions of the complexity classes P, NP, and NP-Complete.
• Introduce the concept of polynomial time reductions.
• Introduce the famous open problem "P versus NP".
• Discuss the origin of the first NP-Complete problem and polynomial time reductions to fill in the known elements of NP-Complete.
• Homework is assigned consisting of readings discussing known NP-Complete problems and established proofs of NP-Completeness, as well as problem sets in which students:
  • show membership of given problems in P and NP;
  • provide explicit polynomial time reductions to show membership in NP-Complete.

RESEARCH & REVISE

• Show the challenge problem is in NP.
• Attempt to show that the challenge problem is not likely to be efficiently solvable in an exact sense
  • Show the problem is NP-hard, and thus NP-Complete.
    • To achieve this, research known NP-Complete problems to identify a candidate for a polynomial time reduction.
    • Provide an explicit polynomial time reduction to show the problem is NP-Complete.
• Describe in layman's terms (as if to the boss) why it is unreasonable to expect an exact solution to the general case of this problem.

TEST YOUR METTLE

Students will group up to show a chain of problems are NP-hard, working towards the goal problem. This will be homework.

GO PUBLIC

Students will present their proof of NP-hardness to the class and receive feedback.

Pre-Lesson Quiz

1. What does it mean for a problem to be polynomial time solvable? Give an example of such a problem.
2. What does it mean for a problem to be non-deterministically polynomial time solvable? Give an example of such a problem.
3. What does it mean for a problem to be NP-Complete?
4. If a problem is polynomial time solvable, is it also non-deterministically polynomial time solvable?
5. If a problem is non-deterministically polynomial time solvable, is it also polynomial time solvable?

Test Your Mettle Quiz

1. Show that the 2-SAT problem is in NP.
2. Show that the 3-SAT problem is in NP.
3. Show either that 1) the 2-SAT problem is in P, or 2) the 2-SAT problem is NP-complete. What would it mean if you were to prove both of these statements?
4. Show either that 1) the 2-color problem is in P, or 2) the 2-color problem is NP-complete. What would it mean if you were to prove both of these statements?
5. Assume that 3-SAT is known to be NP-complete. Use this fact to show that the 3-color problem is NP-complete.
6. Assume 3-color is NP-complete. Use this fact to show that the 4-color problem is NP-complete.
7. Show that the k-color problem, for any constant k, is NP-complete.
8. Show that the Hamiltonian Cycle problem is in NP.
9. Suppose the Hamiltonian Cycle problem has a polynomial time solution. Show that this implies that the problem of finding a Hamiltonian Cycle (listing the vertices that constitute a Hamiltonian Cycle if one exits) would also have a polynomial solution. Do these problems actually have polynomial time solutions? Why or why not?
10. Show that the k-CLIQUE problem is in NP.
11. Show that k-CLIQUE is NP-Complete by providing an explicit polynomial time reduction from 3-SAT.
12. Show that the Traveling Salesperson problem is in NP.
13. Show that the Traveling Salesperson problem is NP-Complete by providing an explicit polynomial time reduction from some known NP-Complete problem.
14. Santa needs some help:

Imagine you are Santa and you want to try to perfectly pack your sleigh with presents. That is, you want to pack up the sleigh with some of the presents from the workshop so that the total weight of the presents on the sleigh is exactly equal to the capacity of the sleigh, no more, no less. Formally, the problem is as follows:

Perfect Christmas Packing Problem:

Input • n Christmas presents, each with weight w1, w2, …, wn • A positive integer k denoting the maximum weight Santa’s sleigh can hold.

Output: Output yes if there is a subset of the n presents whose total weight sums to exactly k. Output no if there is no such subset.

1. Design a O(nk) run-time algorithm to solve this problem.
2. Is the Christmas Packing Problem in NP?
3. Is the Christmas Packing Problem in P?
4. Is the Christmas Packing Problem NP-Complete?