ماذا يعني NP في الخوارزميات وهياكل البيانات؟ شرح مبسّط
اختصار NP يعني «الوقت متعدد الحدود غير الحتمي» (Non-deterministic Polynomial time)، وهو يصف مجموعة المسائل التي إذا أعطاك أحدهم حلاً مقترحاً لها، استطعت التحقق من صحته بسرعة (في زمن متعدد الحدود)، حتى لو كان إيجاد هذا الحل من الصفر صعباً جداً. باختصار: التحقق سهل، والاكتشاف قد يكون مرهقاً.
قبل أي شيء، لنصحّح أشيع خطأ حول هذا المصطلح.
تنبيه: NP لا تعني «غير متعدد الحدود»
كثيرون يظنون أن الحرف N في NP يعني Non-polynomial أي «ليست متعددة الحدود» أو «بطيئة». هذا خطأ شائع. الحرف N يشير إلى non-deterministic (غير حتمي)، وهو نموذج نظري لآلة تستطيع «تخمين» الحل الصحيح ثم التحقق منه. لذلك فإن كل مسألة سهلة الحل هي أيضاً داخل NP؛ فئة NP أوسع من P وليست منفصلة عنها.
ما الفرق بين P و NP؟
- P: المسائل التي يمكن حلّها بكفاءة، أي في زمن متعدد الحدود مثل O(n²) أو O(n log n). مثال: ترتيب قائمة أرقام، أو البحث عن أقصر طريق بين نقطتين باستخدام خوارزمية Dijkstra.
- NP: المسائل التي يمكن التحقق من صحة حلٍّ معطى لها بكفاءة، بغضّ النظر عن صعوبة إيجاده.
العلاقة المؤكدة رياضياً هي أن كل مسألة في P موجودة في NP (لأن ما تستطيع حلّه بسرعة تستطيع التحقق منه بسرعة). السؤال المفتوح هو العكس: هل كل مسألة يسهل التحقق منها يسهل حلّها أيضاً؟
معضلة P مقابل NP
هذا هو السؤال الأشهر في علوم الحاسوب، وأحد مسائل الألفية السبع التي رصدت لها جائزة مليون دولار. السؤال ببساطة: هل P = NP؟
إذا ثبت أن P = NP، فهذا يعني أن كل مسألة يسهل التحقق من حلّها يمكن أيضاً حلّها بسرعة. النتيجة ستكون زلزالاً: كثير من أنظمة التشفير الحديثة تعتمد على صعوبة حلّ مسائل معيّنة، فلو أصبح حلّها سهلاً لانهار أساس أمان البنوك والاتصالات. حتى عام 2026، لم يُثبت أحد أياً من الاتجاهين، والاعتقاد السائد بين الباحثين هو أن P ≠ NP، لكن دون برهان.
المصطلحات المتشابهة: تفريق سريع
| المصطلح | المعنى المختصر |
|---|---|
| P | يُحلّ بكفاءة (زمن متعدد الحدود) |
| NP | يُتحقق من حلّه بكفاءة |
| NP-Complete | أصعب مسائل NP؛ حلّ أيٍّ منها بكفاءة يحلّها جميعاً |
| NP-Hard | صعبة بقدر مسائل NP على الأقل، وقد لا تنتمي إلى NP أصلاً |
فكرة NP-Complete جوهرية: لو وجدت خوارزمية سريعة لمسألة واحدة منها فقط، لأثبتّ تلقائياً أن P = NP وحللت الجميع. أما NP-Hard فقد تكون أصعب من أن يُتحقق حتى من حلولها بسرعة.
أمثلة على مسائل NP
- مسألة البائع المتجول (TSP): إيجاد أقصر مسار يمرّ بكل المدن مرة واحدة ويعود. التحقق من طول مسار مقترح سهل، لكن إيجاد الأقصر بين ملايين الاحتمالات مكلف.
- مسألة الحقيبة (Knapsack): اختيار أشياء بأقصى قيمة دون تجاوز وزن محدد.
- تلوين الرسم البياني: هل يمكن تلوين العُقد بثلاثة ألوان دون أن يتشارك عقدتان متجاورتان اللون نفسه؟
- SAT: هل توجد قيم منطقية تجعل تعبيراً منطقياً معيناً صحيحاً؟ وهي أول مسألة أُثبت أنها NP-Complete.
لاحظ القاسم المشترك: عدد الاحتمالات ينفجر أُسّياً مع حجم المدخلات، بينما فحص احتمال واحد يبقى سريعاً.
كيف نتعامل معها عملياً؟
بما أننا لا نملك خوارزميات سريعة مضمونة لهذه المسائل، نلجأ إلى بدائل واقعية:
- الخوارزميات التقريبية: تعطي حلاً قريباً من الأمثل مع ضمان رياضي لمدى الاقتراب، وهي كافية في أغلب التطبيقات.
- الخوارزميات الجشعة (Greedy): تختار أفضل قرار محلي في كل خطوة؛ سريعة لكنها لا تضمن الحل الأمثل دائماً.
- الاستدلال (Heuristics) والخوارزميات فوق الاستدلالية: مثل خوارزميات المستعمرات والخوارزميات التطورية والمحاكاة، مفيدة حين يكون «حل جيد بسرعة» أهم من «الحل المثالي».
- البرمجة الديناميكية والتقليم (Branch & Bound): تحلّ حالات صغيرة أو متوسطة بدقة عبر استبعاد الفروع غير الواعدة مبكراً.
نصيحة عملية من واقع التطبيق: قبل أن تظن أن مسألتك «مستحيلة»، تحقّق من حجم المدخلات الفعلي. كثير من المسائل NP-Complete تُحلّ بدقة تامة عند الأحجام الصغيرة أو المتوسطة، وقد لا تحتاج إلى حلٍّ تقريبي إطلاقاً. الخطأ الشائع هو استخدام خوارزمية تقريبية معقّدة على بيانات صغيرة كان يكفيها حلّ دقيق مباشر.
الأسئلة الشائعة
هل NP تعني أن المسألة غير قابلة للحل؟ لا. كل مسائل NP قابلة للحل نظرياً؛ المشكلة في الزمن الذي قد يطول كثيراً مع كبر المدخلات، وليس في استحالة الحل.
هل كل مسألة في NP هي NP-Complete؟ لا. مسائل P موجودة داخل NP لكنها ليست NP-Complete. المسائل NP-Complete هي الأصعب ضمن NP فقط.
لماذا يهتم المبرمج العادي بهذا الموضوع؟ لأنه يساعدك على التعرّف مبكراً على أن مسألة ما «صعبة جوهرياً»، فتوفّر وقتك بالبحث عن حل تقريبي بدل مطاردة حل مثالي سريع قد لا يكون موجوداً أصلاً.
ما الفرق بين NP-Hard وNP-Complete؟ كل مسألة NP-Complete هي NP-Hard وتنتمي إلى NP. أما NP-Hard فقد تكون خارج NP، أي صعبة لدرجة أن التحقق من حلّها نفسه ليس بالضرورة سريعاً.