NP-Completeness
এনপি-সম্পূর্ণতা
NP-এর সবচেয়ে কঠিন সমস্যাদের class — NP-তে থাকা, এবং NP-এর প্রতিটা সমস্যা এতে polynomial-time reduce করা যায়। একটা NP-complete সমস্যার polynomial solution পেলে সবগুলোরই পাওয়া যায়।
also: NP-complete, NPC
একটা সমস্যা L NP-complete যদি দুইটা শর্ত একসাথে সত্য: (১)
L ∈ NP (certificate থাকলে polynomial সময়ে যাচাইযোগ্য), আর (২)
L NP-hard (NP-এর প্রতিটা সমস্যা L-এ polynomial-time
reduce করা যায়)।
Reduction transitivity-ই কাঠামোটা গড়ে তোলে। একবার SAT
NP-complete প্রমাণিত হলে (Cook-Levin theorem), নতুন যেকোনো সমস্যা
X-কে NP-complete প্রমাণ করতে শুধু একটা SAT \le_p X (বা যেকোনো
জানা NP-complete সমস্যা থেকে) reduction যথেষ্ট — পুরো প্রমাণ নতুন
করে করতে হয় না।
৩০০০-এর বেশি সমস্যা এভাবে NP-complete প্রমাণিত — SAT, 3-SAT, Vertex Cover, Independent Set, Hamiltonian Path, Graph Coloring, Subset Sum, Bin Packing, TSP (decision version), Knapsack (decision version)।
ব্যবহারিক তাৎপর্য: একটা নতুন সমস্যাকে NP-complete প্রমাণ করা মানে “exact polynomial algorithm খোঁজায় সময় নষ্ট করবেন না — সরাসরি approximation/heuristic/randomization-এ যান” — এটাই algorithm design-এর একটা সবচেয়ে ব্যবহারিক negative ফলাফল।
সতর্কতা: NP-hard ⊋ NP-complete (subset নয়, superset) — কিছু সমস্যা (যেমন undecidable Halting Problem) NP-hard কিন্তু NP-এর ধারেকাছেও নেই।