Dalam teori komputasi dikenal beberapa kelas problema. Salah satu dari kelas-kelas tersebut adalah kelas NP—problem. Di daiam kelas ini terdapat himpunan problema—problema dimana sampai saat ini belum dapat ditemukan alqoritma—algoritma penyelesaian untuk masing—masing problema tersebut yaitu dapat bekerja dalam waktu polinormial agar menghasilkan solusi yang optimal. Selain kelas HP-problem terdapat kelas lain yaitu kelas HP—Complete. Kelas ini merupakan sebuah himpunan problema—problema yang paling berat (the hardest problem) dari himpunan problema-problema di dalam kelas HP—problem. Artinya jika dapat ditemukan algoritma penyelesaian yang bekerja dalam waktu polinomial untuk menghasilkan solusi optimal bagi salah satu anggota kelas ini maka seluruh kelas MP—problem akan dapat pula ditemukan algoritma penyelesaiannya yang polinomial untuk memperoleh solusi yang optimal. Dalam menentukan apakah sebuah anggota HP—problem termasuk di dalam HP—Complete dipergunakan suatu teknik pembuktian yang disebut reduksi. Teknik inilah yang dibahas dan merupakan inti dari tulisan berikut.