ماذا تعني NP؟

NP تعني زمن متعدد الحدود غير حتمي (nondeterministic polynomial time). وبشكل مكافئ، تكون المشكلة ضمن NP إذا كان يمكن التحقق من حل مقترح في زمن متعدد الحدود، حتى لو بدا العثور عليه صعبًا. مسار البائع المتجول الأقل من طول معين سهل التحقق بمجرد إعطائه ولكنه يبدو صعب الاكتشاف.

كيف تثبت أن مشكلة جديدة هي مشكلة كاملة غير قطعية؟

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

الكماليات غير القطعية (NP-Completeness) والاختزالات

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

اعثر على موضوع باستخدام PaperMindقريبًاFind papers & topics

Tools & resources

تنزيل الشرائح

Learn & explore

فيديوقريبًا

Definition

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

Scope

يغطي هذا الموضوع فئة NP من المشكلات التي يمكن التحقق منها في زمن متعدد الحدود، والاختزالات المتعددة الحدود من نوع واحد، ونظرية كوك-ليفين التي تثبت أن قابلية الإرضاء (satisfiability) هي مشكلة كاملة غير قطعية، وكتالوج كارب للمشكلات التوافقية الكاملة غير القطعية، ومنهجية إثبات أن مشكلات جديدة هي كاملة غير قطعية عن طريق الاختزال من مشكلات معروفة.

Core questions

ماذا يعني أن تكون مشكلة ما من بين الأصعب في NP؟
كيف تحدد نظرية كوك-ليفين أول مشكلة كاملة غير قطعية؟
كيف تُستخدم الاختزالات لإثبات أن مشكلة جديدة هي مشكلة كاملة غير قطعية؟
لماذا تترتب على الكمالية غير القطعية لمشكلة واحدة آثار على آلاف المشكلات الأخرى؟

Key theories

نظرية كوك-ليفين: قابلية الإرضاء البوليانية (Boolean satisfiability) هي مشكلة كاملة غير قطعية لأن حساب أي مدقق متعدد الحدود زمنيًا يمكن ترميزه كحالة قابلية إرضاء، مما يوفر المشكلة الكاملة الأساسية التي تُشتق منها المشكلات الأخرى.
اختزالات كارب وشبكة المشكلات الكاملة غير القطعية: أظهر كارب أن إحدى وعشرين مشكلة طبيعية، من تلوين الرسوم البيانية إلى مشكلة قرار البائع المتجول، هي مشكلات كاملة غير قطعية عن طريق اختزالات متعددة الحدود زمنيًا، مما أطلق ممارسة إثبات الصعوبة من خلال شبكة متنامية من الاختزالات.

Clinical relevance

الكماليات غير القطعية (NP-completeness) هي التشخيص العملي لعدم القابلية للحل: بمجرد إثبات أن مشكلة في الجدولة، أو اللوجستيات، أو التصميم، أو التحقق هي مشكلة كاملة غير قطعية، يتوقف المهندسون عن البحث عن خوارزمية دقيقة سريعة مضمونة ويتجهون إلى خوارزميات التقريب، أو الاستدلالات (heuristics)، أو حلول البرمجة العددية الصحيحة، أو القيود التي تجعل المشكلة قابلة للحل.

History

أثبت كوك أن قابلية الإرضاء (satisfiability) هي مشكلة كاملة غير قطعية في عام 1971، وحصل ليفين بشكل مستقل على نتائج مكافئة في الاتحاد السوفيتي. في عام 1972، أظهر كارب إحدى وعشرين مشكلة أخرى كاملة غير قطعية، كاشفًا عن انتشار الظاهرة وجاعلًا الكماليات غير القطعية الأداة المركزية لتشخيص الصعوبة الحسابية.

Key figures

Stephen Cook
Leonid Levin
Richard Karp

Seminal works

cook1971
karp1972

Frequently asked questions

ماذا تعني NP؟: NP تعني زمن متعدد الحدود غير حتمي (nondeterministic polynomial time). وبشكل مكافئ، تكون المشكلة ضمن NP إذا كان يمكن التحقق من حل مقترح في زمن متعدد الحدود، حتى لو بدا العثور عليه صعبًا. مسار البائع المتجول الأقل من طول معين سهل التحقق بمجرد إعطائه ولكنه يبدو صعب الاكتشاف.
كيف تثبت أن مشكلة جديدة هي مشكلة كاملة غير قطعية؟: تُظهر أمرين: أن المشكلة تقع ضمن NP، بحيث يمكن التحقق من الحلول المرشحة بسرعة، وأن بعض المشكلات الكاملة غير القطعية المعروفة تختزل إليها في زمن متعدد الحدود. ينقل الاختزال الصعوبة المعروفة، مما يضع المشكلة الجديدة ضمن الأصعب في NP.