Kim, Y. E. and Lee, G. M. (2003). NP-Completeness: An Overview. Lecture Notes, November 2003.
This paper presents an overview of NP-complete problems. The theory of NP-completeness is important not only in the theoretical aspect but also in reality. First, we will take a look at the formal definition and some examples of NP-complete problems. Then, we will see how to prove a problem is NP-complete and how to cope with NP-complete problems.