مسألة كثيرة حدود غير قطعية كاملة
من ويكيبيديا، الموسوعة encyclopedia
في الرياضيات صنف التعقيد، تعرف المسائل كثيرة الحدود غير القطعية الكاملة (NP-complete problems)، بأنها كل ما يحقق الشرطين الآتيين:
- لكل لغة،L, موجودة في NP يوجد دالة بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f :
معلومات سريعة صنف فرعي من, جزء من ...
مسألة كثيرة حدود غير قطعية كاملة
صنف فرعي من | |
---|---|
جزء من | |
جانب من جوانب | |
ممثلة بـ | |
لديه جزء أو أجزاء |
إغلاق
إذا وإذا
- المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A.
أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة.