🎛️ الجدار الأسي
زِد حجم المسألة n. قارن زمن الحل حسب تعقيد الخوارزمية. الكثير الحدود يبقى قابلًا للتدبير، بينما الأسي ينفجر.
O(n) خطي
20 ns
O(n²) تربيعي
400 ns
O(2ⁿ) أسي
1 µs
O(n!) عاملي
—
عند n = 20، الكثير الحدود فوري والأسي لا يزال قابلًا للتدبير. زِد n لترى الجدار.
🔍 P و NP : عالمان من المسائل
في علوم الحاسوب النظرية، نصنف المسائل حسب تعقيدها: كم عدد العمليات اللازمة لحلها بدلالة حجم المُدخَل n؟
- الصنف P (Polynomial time / الزمن الكثير الحدود) : مسائل قابلة للحل في زمن كثير الحدود. لمُدخَل حجمه n، توجد خوارزمية بـ O(n^k) من أجل قيمة k ثابتة معينة. أمثلة: ترتيب لائحة (O(n log n))، إيجاد أقصر مسار (دييكسترا، O((V+E) log V))، حل نظام خطي (غاوس، O(n³)).
- الصنف NP (Nondeterministic Polynomial time) : مسائل يمكن التحقق من حل مُرشَّح لها في زمن كثير الحدود. لكن إيجاد هذا الحل قد يكون أطول بكثير. أمثلة: سودوكو، التاجر المتجول، تفكيك عدد كبير إلى عوامل.
سؤال P مقابل NP :
هل كل مسألة يكون حلها قابلًا للتحقق في زمن كثير الحدود
هو أيضًا قابل للحل في زمن كثير الحدود؟
بعبارة أخرى : P = NP أم P ≠ NP ؟
🎓 1971 : كوك وليفين يطرحان المسألة
ستيفن كوك (تورنتو، 1971) وليونيد ليفين (الاتحاد السوفيتي، 1973، بشكل مستقل) ينشران أسس النظرية. كوك يُدخِل مفهوم اكتمال NP (NP-complétude) :
تكون المسألة تامة في NP (NP-complète) إذا كانت ضمن NP وإذا كانت جميع مسائل NP الأخرى قابلة للرد إليها في زمن كثير الحدود. بعبارة أخرى : إنها إحدى أصعب مسائل NP. إذا حللنا بكفاءة مسألة واحدة فقط تامة في NP، فإننا نحل بكفاءة جميع مسائل NP.
يبرهن كوك أن SAT (قابلية الإرضاء البوليانية) تامة في NP. إنه أول مثال تاريخي.
🏆 أمثلة على مسائل تامة في NP
- SAT (قابلية الإرضاء البوليانية) : بإعطاء صيغة بوليانية، هل توجد إسناد للمتغيرات يجعلها صحيحة؟ مسألة كوك الأصلية (1971).
- التلوين بثلاثة ألوان : هل يمكن تلوين مبيان بـ 3 ألوان دون أن يتشارك جاران اللون نفسه؟ (بـ 4 ألوان، يكون ذلك ممكنًا دائمًا — مبرهنة رأيناها قبل قليل. أما بـ 3 ألوان، فهي تامة في NP.)
- التاجر المتجول (TSP) : إيجاد أقصر دورة تزور n مدينة مرة واحدة بالضبط.
- حقيبة الظهر : الاختيار من بين أشياء معطاة بوزن/قيمة لتعظيم القيمة دون تجاوز سعة معينة.
- سودوكو المعمَّم (n²×n²) : تامة في NP.
- مسألة هاميلتون : إيجاد دورة تمر بكل رأس من مبيان مرة واحدة.
- Subset Sum (مجموع المجموعة الجزئية) : بإعطاء أعداد صحيحة وهدف S، إيجاد مجموعة جزئية مجموعها يساوي S.
- كانسة الألغام، تتريس، باك-مان : نسخها المعممة صعبة في NP (NP-difficiles).
اليوم، نعرف أكثر من 3000 مسألة تامة في NP. تأتي من جميع المجالات : المنطق، نظرية المبيانات، الأمثلة، البيولوجيا، الاقتصاد، التعمية.
💰 2000 : إحدى مسائل الألفية السبع
في عام 2000، صنّف معهد كلاي للرياضيات مسألة P مقابل NP ضمن مسائله السبع للألفية. مليون دولار لمن يحل المسألة في أحد الاتجاهين أو الآخر.
قناعة شبه إجماعية لدى الباحثين : P ≠ NP. لكن لا برهان. استطلاع من 2019 شمل 152 خبيرًا أعطى 88 % لصالح P ≠ NP، و12 % لصالح P = NP أو عدم القابلية للحسم.
🔮 العواقب إذا كان P = NP
تخيل أن عالم رياضيات يبرهن P = NP بخوارزمية كثيرة الحدود بنّاءة لـ SAT. آثار متتالية :
- التعمية مكسورة : RSA و ECC و AES (المفاتيح) تعتمد على كون تفكيك أو عكس بعض المسائل صعبًا. إذا كان P = NP، نفكك بسرعة ← تنهار جميع أنظمة التشفير الحالية. بيتكوين، البنوك على الإنترنت، الاتصالات العسكرية : مخترَقة بين عشية وضحاها.
- أمثلة شاملة : جولات التسليم، التخطيط الصناعي، الجدولة، تخصيص الموارد — كلها محلولة في زمن كثير الحدود.
- البيولوجيا : طي البروتينات (AlphaFold من DeepMind تقريب عبقري، لكن المسألة الدقيقة صعبة في NP). تصميم الأدوية، الجينوميات.
- الذكاء الاصطناعي : التعلم الأمثل، الاستدلال الآلي. ذكاء اصطناعي قادر على برهنة المبرهنات الرياضية بنفس كفاءة تحققه منها.
- الرياضيات : إيجاد برهان بطول محدود يصبح بديهيًا. كثير من الحدسيات ستنهار (أو تُحل).
- الاقتصاد : أسواق ذات كفاءة، أمثلة شاملة، توازن عام.
🛡️ العواقب إذا كان P ≠ NP
الفرضية المعيارية. إذا برهنّاها شكليًا :
- التعمية مُثبَتة : تبقى أنظمة تشفيرنا آمنة في جوهرها (على الأقل كلاسيكيًا — يبقى الحاسوب الكمومي تهديدًا منفصلًا).
- حدود الذكاء الاصطناعي : ستبقى بعض المسائل صعبة في جوهرها، حتى لأكثر أنظمة الذكاء الاصطناعي تقدمًا. الأمثلة المثالية بعيدة المنال.
- حرية الإبداع : لو كان إيجاد البراهين الأنيقة سهلًا كثير الحدود بقدر سهولة التحقق منها، لفقد الإبداع الرياضي سرّه. P ≠ NP، هي أيضًا كرامة الابتكار.
🌟 ما وراء P و NP
« حديقة حيوانات التعقيد » تضم اليوم أكثر من 500 صنف معروف. بعض الأصناف الأخرى :
- co-NP : مسائل يكون عدم حلها قابلًا للتحقق بسرعة. سؤال مفتوح : NP = co-NP ؟
- PSPACE : مسائل قابلة للحل بفضاء ذاكرة كثير الحدود. تحتوي NP. سؤال مفتوح : NP = PSPACE ؟
- EXPTIME : زمن أسي. نعلم أن P ⊊ EXPTIME (مبرهنة التراتبية الزمنية).
- BQP (Bounded-error Quantum Polynomial) : مسائل قابلة للحل بكفاءة بواسطة حاسوب كمومي. تحتوي التفكيك إلى عوامل (شور 1994). سؤال : BQP ⊋ P ؟ على الأرجح نعم، لكن غير مبرهن.
- #P : عدّ الحلول بدلًا من إيجاد واحد منها. أصعب بكثير من NP بشكل عام.
- غير قابلة للحسم : مسائل لا توجد لها أي خوارزمية (مسألة التوقف لتورينغ). ما وراء كل شيء.
🚧 لماذا برهنتها صعبة إلى هذا الحد
تم تحديد عدة حواجز نظرية :
- حاجز النسبية (relativisation) (بيكر-غيل-سولوفاي 1975) : بعض البراهين « ستنجح لوحيات (oracles) تعطي P = NP، وأخرى لـ P ≠ NP ». إذن لا تقنية « محلية » يمكنها الحسم.
- حاجز البراهين الطبيعية (رازبوروف-روديتش 1997) : تحت فرضية تعمية معيارية، لا يمكن لأي برهان « طبيعي » أن يبرهن P ≠ NP.
- حاجز الجبرنة (algébrisation) (آرونسون-ويغدرسون 2008) : حتى الطرق الجبرية المتطورة لا تكفي.
الخلاصة : سيتطلب الأمر مقاربة جديدة جذريًا. لهذا السبب يعتقد كثيرون أننا ما زلنا بعيدين عن حل.
📐 الرابط مع برنامجك
- المنطق : SAT هي المسألة التامة في NP الأساسية. المنطق القضوي يُدرَّس ضمنيًا في البرهان (و، أو، نفي، استلزام).
- العدّ (التأليفيات) : فهم لماذا ينمو 2ⁿ أسرع من أي n^k أمر أساسي. برنامج العدّ في الثانية بكالوريا.
- المتتاليات : مقارنة النمو الكثير الحدود مقابل الأسي مقابل العاملي. النهاية والمقارب. برنامج الثانية بكالوريا علوم رياضية.
- الترجع (Récurrence) : معظم الخوارزميات الصعبة في NP لها صياغة ترجعية (التراجع، التفريع والتحديد).
- الاحتمالات : الخوارزميات الاحتمالية (مونت كارلو، لاس فيغاس) تتيح تجاوزًا جزئيًا لصعوبة بعض المسائل الصعبة في NP.
🎯 في الواقع العملي : كيف نتدبر أمرنا؟
إذا كان P ≠ NP، فكيف نحل المسائل الصعبة في NP في الحياة الواقعية؟
- التقريب : إيجاد حل بـ 1.5× الأمثل بدلًا من الأمثل الدقيق. بالنسبة للتاجر المتجول، تضمن خوارزمية كريستوفيدس 1.5×.
- الكشوفات (Heuristiques) : التلدين المحاكى، الخوارزميات الجينية، البحث المحلي. لا ضمان، لكنها غالبًا ممتازة عمليًا.
- حلّالات SAT الحديثة : Z3 (مايكروسوفت)، MiniSat، CryptoMiniSat — تحل أمثلة بملايين المتغيرات، بينما تبقى أسوأ حالة 2ⁿ.
- حالات خاصة : بعض الحالات الجزئية لمسائل صعبة في NP تصبح كثيرة الحدود (2-SAT، التلوين بلونين).
- تعلم الآلة : AlphaFold من DeepMind (طي البروتينات)، AlphaGo (لعبة غو)، AlphaProof (البراهين الرياضية) — تحل عمليًا مسائل صعبة في NP شكليًا.