Previously, we defined the deterministic and nondeterministic complexity classes in the preceding chapters. Now, we establish the concept of polynomial-time many-one reductions. We use this concept to compare languages in terms of their difficulty. The concept induces a partial order among the languages. The \(\mathrm {NP}\) -complete problems have the highest order among the languages in \(\mathrm {NP}\) . Tens of thousands of \(\mathrm {NP}\) languages having practical importance are \(\mathrm {NP}\) -complete. This chapter presents some basic \(\mathrm {NP}\) -complete problems.