مسائل كارب الـ 21 الكاملة من فئة NP

في نظرية التعقيد الحسابي ، تُعدّ مسائل كارب الـ 21 من فئة NP-complete مجموعةً من المسائل الحسابية التي تُصنّف ضمن فئة NP-complete . في بحثه المنشور عام 1972 بعنوان "الاختزال بين المسائل التوافقية" ^{[ 1 ]} ، استخدم ريتشارد كارب نظرية ستيفن كوك لعام 1971 التي تنص على أن مسألة إرضاء الصيغ المنطقية هي مسألة NP-complete ^{[ 2 ]} (وتُعرف أيضًا بنظرية كوك-ليفين ) لإثبات وجود اختزال متعدد الحدود من مسألة إرضاء الصيغ المنطقية إلى كلٍّ من المسائل الحسابية الـ 21 في مجالي التوافقية ونظرية الرسوم البيانية ، مُظهرًا بذلك أنها جميعًا مسائل NP-complete. كان هذا أحد أوائل البراهين على أن العديد من المسائل الحسابية الطبيعية التي تظهر في علوم الحاسوب غير قابلة للحل حسابيًا ، وقد حفّز هذا الاهتمام بدراسة مسألة NP-complete ومسألة P مقابل NP .

تُعرض أدناه مسائل كارب الـ 21، مع احتفاظ العديد منها بأسمائها الأصلية. ويشير التداخل إلى اتجاه عمليات الاختزال المستخدمة. على سبيل المثال، تم إثبات أن مسألة حقيبة الظهر (Knapsack ) هي مسألة كاملة من فئة NP عن طريق اختزال مسألة الغطاء الدقيق (Exact cover) إلى مسألة حقيبة الظهر .

• قابلية الإرضاء : مشكلة قابلية الإرضاء المنطقية للصيغ في الشكل الطبيعي الاقتراني (يشار إليها غالبًا باسم SAT)
  • البرمجة العددية 0-1 (نوع من البرمجة حيث يجب استيفاء القيود فقط، دون أي تحسين)
  • الزمرة (انظر أيضًا مسألة المجموعة المستقلة )
    • مجموعة التعبئة
    • غطاء فيرتكس
      • غلاف المجموعة
      • مجموعة عقدة التغذية الراجعة
      • مجموعة قوس التغذية الراجعة
      • دائرة هاميلتون الموجهة (اسم كارب، وتسمى الآن عادة دورة هاميلتونية موجهة )
        • دائرة هاميلتون غير الموجهة (اسم كارب، وتسمى الآن عادة دورة هاميلتون غير الموجهة )
  • إمكانية الإرضاء بحد أقصى 3 متغيرات حرفية لكل جملة (ما يعادل 3-SAT)
    • العدد اللوني (يُسمى أيضاً مسألة تلوين الرسم البياني )
      • غلاف كليك
      • الغلاف الأصلي
        • مجموعة الضرب
        • شجرة شتاينر
        • المطابقة ثلاثية الأبعاد
        • حقيبة الظهر (تعريف كارب لحقيبة الظهر أقرب إلى مجموع المجموعات الفرعية )
          • تسلسل المهام
          • تقسيم
            • قصّة ماكس

مع مرور الوقت، تبيّن أن العديد من هذه المسائل يُمكن حلّها بكفاءة إذا اقتصرت على حالات خاصة، أو يُمكن حلّها ضمن نسبة مئوية ثابتة من النتيجة المثلى. مع ذلك، بيّن ديفيد زوكرمان في عام ١٩٩٦ أن لكل مسألة من هذه المسائل الـ ٢١ نسخةً مُقيدة للتحسين يستحيل تقريبها ضمن أي عامل ثابت إلا إذا كانت P = NP، وذلك من خلال إظهار أن منهج كارب في الاختزال يُعمّم على نوع مُحدد من اختزال قابلية التقريب. ^{[ ٣ ]} مع ذلك، قد تختلف هذه النسخ عن نسخ التحسين القياسية للمسائل، والتي قد تحتوي على خوارزميات تقريب (كما في حالة القطع الأقصى).

• قائمة مسائل NP-كاملة

• كوك، ستيفن (1971). "تعقيد إجراءات إثبات النظريات" . وقائع الندوة السنوية الثالثة لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC) . الصفحات 151-158 . doi : 10.1145/800157.805047 . ISBN  9781450374644. S2CID 7573663 . 
• كارب، ريتشارد م. (1972). "قابلية الاختزال بين المسائل التوافقية" (ملف PDF) . في: ر. إي. ميلر؛ ج. و. ثاتشر؛ ج. د. بولينجر (محررون). تعقيد الحسابات الحاسوبية . نيويورك: بلينوم. ص 85-103 . doi : 10.1007/978-1-4684-2001-2_9 . ISBN  978-1-4684-2003-6.{{cite book}}: CS1 maint: publisher location ( link )
• زوكرمان، ديفيد (1996). "حول الصيغ غير القابلة للتقريب لمسائل NP-Complete" . مجلة SIAM للحوسبة . 25 (6): 1293-1304 . doi : 10.1137/S0097539794266407 .