نظرة عامة شاملة حول مسألة كثيرة حدود غير قطعية كاملة

في الرياضيات صنف التعقيد، تعرف المسائل كثيرة الحدود غير القطعية الكاملة (NP-complete problems)، بأنها كل ما يحقق الشرطين الآتيين:



لكل لغة،L, موجودة في NP يوجد دالة







f

:



Σ



∗





→



Σ



∗









{\displaystyle f:\Sigma ^{*}\rightarrow \Sigma ^{*}}



بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f :

إذا







f

(

x

)

∈

A



⟺



x

∈

L





{\displaystyle f(x)\in A\iff x\in L}



وإذا







f

(

x

)

∉

A



⟺



x

∉

L





{\displaystyle f(x)\notin A\iff x\notin L}





المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A.

أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة.