Reduksiya - A muammoni kiritishlarni ko'paytma vaqt algoritmidan foydalanib, B muammosining ekvivalent kirishiga aylantirish jarayoni. Ekvivalent degani, A va B muammolari kirish va o'zgartirilgan kirish uchun bir xil javobni (Ha yoki Yo'q) berishi kerak. A dan B gacha qisqartirish algoritmining mavjudligi quyidagilarni nazarda tutadi:
1. Agar B ∈ P bo'lsa, u holda A ∈ P (ko'paytmali vaqt ichida A dan B gacha qisqartirishingiz mumkin va B polinomik vaqt ichida echishingiz mumkin. Buni birlashtirish A uchun ko'p vaqtli algoritmni beradi)
2. Agar B ∈ NP bo'lsa, unda A ∈ NP
3. Agar A NP-qattiq bo'lsa, B - NP-qattiq. A ko'paytirilgan vaqt ichida B ga kamayishi mumkin va agar B NP-qiyin bo'lmasa, u B B NP-NP-qiyin va bu A ∈ NP-NP-qattiq, bu farazga zid (A-NP-qiyin) degan ma'noni anglatadi.
NP-to'liqligi - agar X ∈ NP va X bo'lsa, NP-qiyin bo'lsa, X muammo NP-tugallanadi.
Muammoning to'liqligini isbotlash 2 bosqichni o'z ichiga oladi. Avval biz muammo NPga tegishli ekanligini ko'rsatishimiz kerak va keyin biz buni NP-qiyinligini ko'rsatishimiz kerak. Bosqichlarni quyidagicha izohlash mumkin:
2-qadam - X-ni ko'rsatish qiyin emas. Ma'lum NP-muammoni X-ga qisqartirish. Demak, biz ko'rgan 3-rasm orqali X bu NP-qiyin ekanligini anglatadi.
Amaliy nuqtai nazardan qiziq bo‘lgan vazifalarning aksariyati, polinomial' (polinomial' vaqt mobaynida ishlovchi) algoritmlar. Ya'ni, n uzunlikdagi kirishda algoritmning ishlash vaqti doimiy k (kirish uzunligidan mustaqil) uchun O(nk) dan oshmaydi. Har bir masalada ushbu xususiyatni qondiradigan yechim algoritmi mavjud emas. Ba'zi masalalarni umuman biron bir algoritm yordamida hal qilib bo‘lmaydi. Bunday masalaning klassik misoli bu “to‘xtash muammosi” (berilgan dastur berilgan kirishda to‘xtashini bilish). Bundan tashqari, ularni hal qiladigan algoritm mavjud bo‘lgan masalalar mavjud, har qanday bunday algoritm uzoq vaqt ishlaydi – uning ishlash vaqti har qanday fiksirlangan k soni uchun O(nk) bo‘la olmadi.
