P مقابل NP: هل العثور على الحل أصعب من التحقق منه؟
التعقيد الحسابي • التشفير • حدود الذكاء
هناك ألغاز قد تحتاج سنوات حتى تجد جوابها، ثم لا تحتاج إلا ثوانٍ لتتأكد أن الجواب الذي أمامك صحيح. والسؤال الذي حيّر علماء الحاسوب لأكثر من نصف قرن هو: هل هذا الفرق حقيقي في طبيعة الحساب… أم أننا فقط لم نعثر بعد على الطريق المختصر؟
تخيل أنك تقف أمام متاهة هائلة.
آلاف الممرات أمامك. كل منعطف يفتح احتمالات جديدة، وكل اختيار خاطئ قد يجبرك على العودة مسافة طويلة.
العثور على المخرج قد يستغرق ساعات.
لكن إذا وقف شخص فوق المتاهة ورسم لك الطريق الصحيح بخط ذهبي، فلن تحتاج إلى الساعات نفسها كي تتأكد منه.
ستتبع الخط بعينيك:
هنا انعطف يمينًا.
هنا يسارًا.
لا جدار يقطعه.
وينتهي فعلًا عند المخرج.
العثور على الطريق كان صعبًا.
التحقق منه كان سهلًا.
هذه الفكرة البسيطة تقف خلف واحدة من أشهر المسائل المفتوحة في الرياضيات وعلوم الحاسوب:
هل P تساوي NP؟
—
المسألة التي لا تسأل إن كان الحاسوب يستطيع… بل كم يحتاج من الوقت
عندما نقول إن الحاسوب يستطيع حل مسألة، فإن العبارة وحدها لا تكفي.
لنفترض أن برنامجًا يستطيع إيجاد الجواب الصحيح، لكنه يحتاج إلى عشرة مليارات سنة.
من الناحية النظرية لدينا خوارزمية.
ومن الناحية العملية ليس لدينا شيء.
لذلك لا يهتم علماء الحاسوب فقط بما يمكن حسابه، بل أيضًا بتكلفة الحساب عندما تكبر المشكلة.
وهنا تظهر الفئة P.
بصورة مبسطة، تضم P مسائل نستطيع حلها بخوارزميات يزداد وقت تشغيلها بطريقة تسمى Polynomial Time — زمن متعدد الحدود.
المعنى العملي المبسط: عندما تكبر المدخلات، لا ينفجر زمن الحل بالسرعة الكارثية التي تجعل المسألة عديمة الجدوى مباشرة.
ثم تأتي NP.
والاسم لا يعني «Not Polynomial» كما قد يوحي الحرفان.
بل يعود إلى Nondeterministic Polynomial Time.
لكن للقارئ غير المتخصص توجد طريقة أسهل لفهمها:
في مسائل NP، إذا أعطاك شخص شهادة للحل، تستطيع التحقق من صحتها في زمن متعدد الحدود.
وهنا تبدأ المفارقة.
قد يكون من السهل أن أريك أن الحل صحيح.
لكن هل يعني ذلك أن هناك أيضًا طريقة سريعة للعثور عليه؟
هذا هو قلب المسألة التي يلخصها معهد كلاي بسؤال قريب جدًا من ذلك: إذا كان التحقق من صحة الحل سهلًا، فهل حل المسألة نفسها سهل أيضًا؟
—
ابحث عن الإبرة… ثم تحقق منها
تخيل أنني أعطيك مجموعة ضخمة من الأرقام وأقول:
هناك مجموعة محددة منها تحقق شرطًا معينًا.
اعثر عليها.
قد تضطر إلى فحص عدد هائل من التركيبات.
لكن إذا أعطيتك أنا التركيبة وقلت:
هذه هي.
فقد تستطيع خلال وقت قصير فحصها والتأكد من أنها تحقق الشرط.
هذه هي الفجوة التي تزعج علماء التعقيد.
إنها تظهر في مسائل تتعلق بالتخطيط، والجدولة، والشبكات، والقيود المنطقية، وتصميم الدوائر، ومسارات معينة داخل الرسوم البيانية.
وفي كل مرة يعود السؤال نفسه:
هل صعوبة البحث عن الحل مختلفة جوهريًا عن سهولة فحصه؟
—
مسألة حفلة يمكن أن تتحول إلى كابوس
لنفترض أنك تنظّم مناسبة كبيرة.
مئات الأشخاص سيحضرون.
لكن لديك قائمة طويلة من القيود:
هذان الشخصان لا يجوز أن يجلسا معًا.
هؤلاء يجب أن يكونوا في مجموعات مختلفة.
هذا الشخص لا يستطيع الجلوس في هذا المكان.
وهذه المجموعة يجب توزيعها وفق شروط إضافية.
إذا أعطاك أحدهم ترتيبًا كاملًا للمقاعد، فقد يكون فحص الشروط أمرًا مباشرًا:
تمر على القائمة وتتحقق.
لكن إنشاء الترتيب الصحيح من الصفر قد يعني البحث وسط عدد فلكي من الاحتمالات.
كلما ازداد عدد الأشخاص، لم تزد المشكلة قليلًا فقط.
قد ينفجر عدد الاحتمالات.
وهنا لا يعود السؤال متعلقًا بسرعة جهازك.
يمكنك مضاعفة قوة الحاسوب عشر مرات أو ألف مرة، بينما يزداد فضاء الاحتمالات بسرعة أكبر بكثير.
يصبح الأمر مثل محاولة إفراغ محيط بملعقة أسرع.
—
لماذا لا نجرب كل الاحتمالات؟
هذه أول إجابة تخطر في الذهن.
الحاسوب سريع.
فليجرّب كل شيء.
لكن عبارة «كل شيء» هي التي تخفي الوحش.
في مسائل كثيرة، يتضاعف عدد الاحتمالات أو ينمو بصورة أشد كلما أضفت عنصرًا جديدًا.
عشرة عناصر قد تكون سهلة.
مئة تصبح صعبة.
ألف قد تجعل البحث الشامل مستحيلًا حتى لو بنيت حواسيب أسرع بكثير مما لدينا اليوم.
المشكلة ليست دائمًا أن الآلة بطيئة.
بل أن الكون الممكن للحلول كبير بصورة لا يمكن ملاحقته بالقوة الغاشمة.
لكن ربما نحن مخطئون.
ربما هناك طريقة عبقرية تتجاوز تجربة جميع الاحتمالات.
وهذا بالضبط ما لم نتمكن من إثباته أو نفيه.
—
ستيفن كوك والباب الذي فتح عام 1971
في عام 1971 نشر عالم الحاسوب ستيفن كوك بحثًا أصبح أحد الأسس الكبرى لنظرية التعقيد الحسابي.
وفي الفترة نفسها ظهرت بصورة مستقلة أعمال ليونيد ليفين المرتبطة بالفكرة ذاتها.
أحد الاكتشافات الحاسمة كان وجود مسائل من نوع خاص نسميه اليوم:
NP-complete — مسائل NP الكاملة.
لفهم أهميتها، تخيل ملايين الأقفال المختلفة.
ثم تكتشف أن فتح قفل واحد معين بطريقة سريعة سيعطيك، من حيث المبدأ، طريقة لتحويل حلول جميع الأقفال الأخرى إليه.
هذا تقريبًا موقع مسائل NP-complete داخل القصة.
إذا وجدنا خوارزمية تعمل في زمن متعدد الحدود لمسألة NP-complete واحدة، فإن النتيجة ستكون:
P = NP
وعندها لن نكون قد وجدنا خدعة لمسألة واحدة.
سنكون قد كشفنا شيئًا أساسيًا عن طبيعة الحساب نفسه.
معهد كلاي ينسب صياغة مشكلة P مقابل NP إلى أعمال كوك وليفين في بدايات السبعينيات، ولا تزال المسألة مفتوحة حتى اليوم.
—
ماذا لو كانت P تساوي NP؟
هنا تبدأ الإثارة.
لكن تبدأ معها أيضًا المبالغات.
يقال أحيانًا:
«إذا ثبت أن P = NP فسوف ينهار الإنترنت.»
الأمر ليس بهذه البساطة.
لكن اكتشاف خوارزميات عملية وسريعة للمسائل المناسبة سيغير أجزاء عميقة من علوم الحاسوب.
مشكلات كانت تبدو بحاجة إلى بحث هائل قد تصبح قابلة للحل بكفاءة أكبر بكثير.
الجدولة المعقدة.
التخطيط اللوجستي.
تصميم بعض الدوائر.
حل أنواع واسعة من مسائل القيود.
البحث في فضاءات ضخمة من الاحتمالات.
وقد تمتد الآثار إلى مسائل في البرهان الآلي والذكاء الاصطناعي والتحسين.
أما التشفير فسيكون أحد أكثر المجالات حساسية.
كثير من أنظمة التشفير الحديثة تعتمد، بأشكال مختلفة، على وجود مسائل حسابية يعتقد أنها صعبة بما يكفي لمنع الخصم من الوصول إلى الأسرار خلال زمن عملي.
إذا تغيرت خريطة الصعوبة الحسابية جذريًا، ستحتاج أجزاء كبيرة من عالم التشفير إلى إعادة تقييم.
لكن من غير الدقيق القول إن إثبات P = NP يعني تلقائيًا أن كل تشفير في العالم ينهار في اللحظة نفسها.
البرهان النظري شيء.
ووجود خوارزمية سريعة وفعالة عمليًا شيء آخر.
—
فحتى كلمة «سريع» تخدعنا
لنفترض أن عالمًا أثبت غدًا أن P = NP.
هل يصبح كل شيء فجأة سهلًا؟
ليس بالضرورة.
«Polynomial Time» مفهوم رياضي.
قد تكون الخوارزمية من الناحية النظرية متعددة الحدود، لكنها تحتوي على أس كبير أو ثوابت تجعل استخدامها على مسائل واقعية غير عملي.
أي أن:
P = NP ستكون ثورة نظرية هائلة.
لكنها لا تعني بالضرورة وجود زر سحري نضغط عليه فتُحل فورًا كل مسألة صعبة.
وهذا التفصيل مهم؛ لأن قصص الرياضيات العظيمة تصبح أحيانًا ضحية لعناوين أكبر من الحقيقة.
—
وإذا كانت P لا تساوي NP؟
هذا هو الاتجاه الذي يعتقد كثير من الباحثين أنه الأقرب إلى الحقيقة.
أي:
P ≠ NP
ومعناه أن هناك بالفعل مشكلات يمكننا التحقق من حلولها بكفاءة، لكن لا توجد طريقة عامة لحلها بالكفاءة نفسها.
عندها تكون الفجوة بين العثور والتحقق حقيقية وليست نتيجة عجز مؤقت في ذكائنا.
سيكون ذلك اكتشافًا عميقًا للغاية.
لأنه سيخبرنا أن بعض المتاهات ليست صعبة لأننا لم نصنع حاسوبًا قويًا بما يكفي.
وليست صعبة لأن المبرمج لم يكن ذكيًا بما يكفي.
إنما لأن هناك حدًا أساسيًا في بنية الحساب.
لكن ثمة مشكلة صغيرة:
لم يثبت أحد ذلك.
يمكن لغالبية المختصين أن تتوقع نتيجة معينة.
أما الرياضيات فلا تجري الانتخابات.
يكفي برهان واحد صحيح لقلب جميع التوقعات.
—
المليون دولار
عندما أعلن معهد كلاي للرياضيات مسائل الألفية السبع عام 2000، خصص صندوق جوائز قيمته سبعة ملايين دولار:
مليون دولار لكل مسألة.
وكانت P مقابل NP واحدة منها. وحتى الآن لم تُحسم رسميًا؛ ومن مسائل الألفية السبع تظل حدسية بوانكاريه وحدها التي حُلّت واعترف بحلها.
لكن كما رأينا في قصة بيرلمان، المليون ليس هو الجائزة الحقيقية.
من يحل P مقابل NP لن يخبرنا فقط كيف نكسب مليون دولار.
سيخبرنا شيئًا لم نعرفه من قبل عن حدود حل المشكلات.
—
ثم جاء عصر الذكاء الاصطناعي
المسألة وُلدت قبل أن يحمل الإنسان حاسوبًا في جيبه.
وقبل محركات البحث.
وقبل الإنترنت الحديث.
وقبل أن تستطيع آلة أن تجيبك بلغة طبيعية، أو تكتب برنامجًا، أو تبحث عن برهان.
لكن ظهور الذكاء الاصطناعي أعاد إلى P مقابل NP نبرة فلسفية جديدة.
لقد اعتدنا أن نقول عن بعض المشكلات:
الإنسان لم يجد الحل بعد.
ثم ظهرت أنظمة تستطيع البحث في احتمالات أكثر منا، والتعلم من كميات هائلة من البيانات، واقتراح حلول لا تخطر سريعًا على العقل البشري.
وهنا يصبح السؤال أكثر دقة:
عندما تعجز آلة ذكية عن مشكلة ما، هل نحتاج إلى آلة أذكى؟
أم أن هناك مسائل لا يغير طبيعتها مقدار الذكاء الذي نلقيه عليها؟
P مقابل NP لا تحدد وحدها حدود الذكاء الاصطناعي، ولا تقدم نظرية عن الإبداع أو الوعي.
لكنها تسأل سؤالًا أكثر أساسية:
ما الذي يمكن الوصول إليه حسابيًا بكفاءة؟
وهذا سؤال سيصبح أهم، لا أقل أهمية، كلما أصبحت آلاتنا أقوى.
—
هل الإبداع مجرد بحث؟
تخيل عالم رياضيات يبحث عن برهان.
ملايين المسارات الممكنة.
تعريفات.
لمّات.
فرضيات.
خطوات يمكن جمعها بطرق لا تكاد تنتهي.
عندما يوضع أمامنا برهان كامل، قد نستطيع فحصه خطوة خطوة.
لكن العثور على البرهان قد يحتاج إلى سنوات من العبقرية.
فهل هناك علاقة بين هذه المفارقة ومسألة P مقابل NP؟
نعم، في بعض مسائل البحث والتحقق الرسمية توجد روابط عميقة بنظرية التعقيد.
لكن يجب ألا نقفز إلى استنتاج أكبر مما تسمح به الرياضيات.
حتى لو ثبت يومًا أن P = NP، فهذا لا يعني أن الحب يمكن حسابه، أو أن الفن يصبح خوارزمية، أو أن كل إبداع بشري يمكن اختزاله إلى بحث سريع.
إنه سيخبرنا شيئًا هائلًا عن فئات محددة من المشكلات الحسابية.
وهذا وحده يكفي.
—
الخط الذهبي في المتاهة
لهذا كان الغلاف متاهة.
ليس لأن كل متاهة مسألة NP-complete.
بل لأنها تقدم لنا الاستعارة الأبسط للفكرة.
أنت في الأسفل.
أمامك آلاف الطرق.
لا تعرف أيها يقود إلى النهاية.
هذه هي لحظة البحث.
ثم يظهر الخط الذهبي.
فجأة لم تعد مهمتك العثور على الطريق.
مهمتك فقط أن تسير بعينيك فوقه وتتأكد أنه لا يخترق جدارًا وأنه يصل إلى المخرج.
هذه هي لحظة التحقق.
والسؤال الذي بقي مفتوحًا منذ بدايات السبعينيات هو:
هل يوجد في كل مرة تقريبًا «خط ذهبي» يمكننا نحن أيضًا اكتشافه بسرعة؟
أم أن هناك مسائل يستطيع من يعرف الجواب أن يقنعنا به بسرعة، بينما يظل اكتشاف الجواب نفسه وراء جدار لا تستطيع أي خوارزمية سريعة تجاوزه؟
لقد بنينا حواسيب أسرع.
وشبكات أضخم.
وذكاءً اصطناعيًا أكثر قدرة.
ووضعنا مليون دولار خلف السؤال.
ومع ذلك، بعد أكثر من نصف قرن، ما زلنا واقفين عند مدخل المتاهة.
ولعل أعمق صيغة للمسألة ليست:
هل P تساوي NP؟
بل السؤال الذي يفهمه كل إنسان بحث يومًا عن حل ثم رآه واضحًا بعد أن كشفه شخص آخر:
لماذا يكون الجواب واضحًا جدًا بعد أن نعرفه… وصعبًا جدًا قبل أن نجده؟