Np-Hard : مسئله ای هستنش که در صورت پیدا شدن الگوریتم از درجه چند جمله ای میشه تمام مسائل NP رو به این مسئله تبدیل کرد و با پیچیدگی چند جمله ای حل کرد.
.
به روشی که مسائل Np به NP_Hard تبدیل میشن Reduction میگیم .
منظور از Reduction اینه که فرض کنید که یک مسئله داریم که یکسری ورودی خاص داره مثلا X و یک مسئله دیگه داریم با ورودی Y حالا اگر بشه X رو بشکلی با درجه چند جمله ای به Y تبدیل کرد اصطلاجا Reduction بهش گفته میشه .
یعنی بطور خلاصه Reduction یعنی تبدیل ورودی یک مسئله به یک مسئله دیگه .
به الگوریتم از درجه چند جمله ای 
(C یک ثابت هستش) . که برای Reduction ( یا تبدیل ورودی ۲ مسئله به هم) استفاده میشه polynomial-time reduction algorithm. میگن .
NP_Complete : مسائلی که هم Np هستند و هم NP_Hard . یعنی هم باید در صورت دادن یک جواب بشه درستی جواب رو در مدت زمان چند جمله ای بررسی کرد و هم بشه بقیه مسائل NP رو به این مسئله کاهش داد .
مثل Knapscak یا پیدا کردن دور همیلتونی در گراف یا traveling-salesman و...
ضمنا تمام مسائل Np-complete با استفاده از Reduction قابل تبدیل به هم هستند .