### Unit 8: NP-Completeness

In this last unit, we will study a special class of problems called the NP-complete problems. Many interesting computational problems are NP-complete, but there are no polynomial-time algorithms known for solving any of them. The unit presents techniques for determining when a problem is NP-complete.

**Completing this unit should take you approximately 11 hours.**

Upon successful completion of this unit, the student will be able to:

- Explain the classification of difficult computer science problems as belonging to P, NP, and NP-hard classes.

### 8.1: Introduction to NP-Completeness

Read Chapter 8 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book

*Algorithms*.

### 8.2: NP-Completeness - Part I

Watch this video to learn about NP-Complete problems in the context of computer algorithms.

### 8.3: NP-Completeness - Part II

Watch this video to learn about NP-Complete problems in the context of computer algorithms.

### 8.4: NP-Completeness - Part III

Watch this video to learn about NP-Complete problems in the context of computer algorithms.

### 8.5: NP-Completeness - Part IV

Watch this video to learn about NP-Complete problems in the context of computer algorithms.

### 8.6: NP-Completeness - Part V

Watch this video to learn about NP-Complete problems in the context of computer algorithms.

Complete all questions in this assignment. There are two questions that are both related to proving NP-Completeness of a given problem. You can check your answers against the Answer Key.