الكمال NP والاستعصاء

يحدد الكمال NP أصعب المشكلات في الفئة NP — تلك التي تختزل إليها كل مشكلة NP — ويوفر الإطار القياسي للتعرف على المشكلات التي لا توجد لها خوارزمية فعالة معروفة أو محتملة.

Definition

تكون مشكلة القرار NP-كاملة إذا كانت تقع ضمن NP (حيث تحتوي حالات 'نعم' الخاصة بها على شهادات يمكن التحقق منها بكفاءة) وكل مشكلة في NP تختزل إليها في وقت متعدد الحدود؛ وتُعد هذه المشكلات الأصعب في NP، وستؤدي خوارزمية زمنية متعددة الحدود لأي منها إلى حل لجميعها.

Scope

يغطي هذا الموضوع فئات التعقيد P و NP، والاختزالات متعددة الحدود الزمنية، وتعريفات الصلابة NP والكمال NP، ونظرية كوك-ليفن التي تثبت أن قابلية الإرضاء هي NP-كاملة، وفهرس كارب لمشكلات NP-كاملة، والعواقب العملية للاستعصاء على تصميم الخوارزميات. يطبق هذه المفاهيم على التعرف على المشكلات الصعبة والتعامل معها؛ وتُعالج النظرية الرسمية الأوسع لفئات التعقيد الحسابي في المجال الفرعي لنظرية الحوسبة.

Core questions

• ما الذي يميز فئات التعقيد P و NP؟
• كيف ينقل الاختزال متعدد الحدود الزمنية الصلابة من مشكلة إلى أخرى؟
• ماذا تثبت نظرية كوك-ليفن، ولماذا تعتبر قابلية الإرضاء محورية؟
• كيف يتم إثبات أن مشكلة جديدة هي NP-كاملة عن طريق الاختزال من مشكلة معروفة؟
• بمجرد إثبات أن مشكلة ما هي NP-صعبة، ما هي الاستراتيجيات الخوارزمية المتبقية؟

Key concepts

• فئة التعقيد P
• فئة التعقيد NP
• اختزال متعدد الحدود الزمنية
• صلابة NP
• كمال NP
• نظرية كوك-ليفن
• قابلية الإرضاء البوليانية (SAT)
• مسألة P مقابل NP

Key theories

نظرية كوك-ليفن

تثبت نظرية كوك-ليفن أن قابلية الإرضاء البوليانية (SAT) هي NP-كاملة: كل مشكلة في NP تختزل إليها في وقت متعدد الحدود، مما يوفر أول مشكلة NP-كاملة والمرتكز لإثبات صعوبة المشكلات الأخرى.

قابلية الاختزال بين المشكلات التوافقية

أظهر كارب أن الاختزالات متعددة الحدود الزمنية تربط العديد من المشكلات الطبيعية — مثل الزمرة، وغطاء الرأس، ودورة هاميلتون، والتقسيم وغيرها — في شبكة من المشكلات NP-كاملة، بحيث يمكن إثبات صعوبة كل منها عن طريق الاختزال من مشكلة أخرى.

Clinical relevance

يُعد إدراك أن مشكلة ما هي NP-كاملة أحد أكثر النتائج فائدة عمليًا في الحوسبة: فهو يخبر المهندسين بعدم توقع خوارزمية دقيقة سريعة، وبدلاً من ذلك، نشر خوارزميات تقريبية، أو استدلالات، أو حلول دقيقة مُعدلة للحالات النموذجية، أو قيود على حالات خاصة قابلة للحل. العديد من مشكلات الجدولة، والتوجيه، والتعبئة، والتصميم هي NP-كاملة.

History

قدم ستيفن كوك الكمال NP في عام 1971، وأثبت أن SAT هي NP-كاملة؛ وتوصل ليونيد ليفن إلى نتائج مماثلة بشكل مستقل. أظهرت ورقة ريتشارد كارب عام 1972 أن 21 مشكلة طبيعية هي NP-كاملة، مما أرسى نطاق الإطار. صنف كتاب غاري وجونسون عام 1979 مئات المشكلات NP-كاملة وأصبح المرجع القياسي.

Debates

P مقابل NP

ما إذا كانت P تساوي NP — أي ما إذا كانت كل مشكلة يمكن التحقق منها بكفاءة قابلة للحل بكفاءة أيضًا — هي المشكلة المفتوحة الأبرز في هذا المجال؛ ويخمن معظم الباحثين أن P لا تساوي NP، لكن السؤال لم يُحل بعد وهو إحدى مشكلات جائزة الألفية.

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

ما الفرق بين NP-صعبة و NP-كاملة؟

تكون المشكلة NP-صعبة إذا كانت كل مشكلة NP تختزل إليها في وقت متعدد الحدود، ولكنها لا تحتاج بالضرورة أن تكون هي نفسها في NP ولا تحتاج أن تكون مشكلة قرار. تكون المشكلة NP-كاملة إذا كانت NP-صعبة وفي NP معًا. المشكلات NP-كاملة هي أصعب المشكلات التي لا تزال في NP.

هل يعني الكمال NP أن المشكلة لا يمكن حلها أبدًا؟

لا. بل يعني أنه لا توجد خوارزمية زمنية متعددة الحدود معروفة لجميع المدخلات ومن المحتمل ألا توجد إذا كانت P لا تساوي NP. عمليًا، تُعالج هذه المشكلات باستخدام خوارزميات التقريب، والاستدلالات، وحلول زمنية أسية تعمل على الحالات الواقعية، أو عن طريق التقييد بحالات خاصة.