P مقابل NP

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

 بعض المسائل تبدو أنها تتطلب عددًا كبيراً من الخطوات الآخذ بالازدياد بشكل سريع. إحدى هذه المسائل هي مسألة المجموعة المستقلة: بالنظر إلى رسم بياني المتكون من نقاط تدعى رؤوسًا وخطوط تربط بين رأسين تدعى أقواساً، تسمى مجموعة الرؤوس مستقلة إذا لم يكن هناك رأسان في المجموعة متصلان بخط. بالنظر إلى رسم بياني وعدد صحيح موجب n، فإن المسألة هي تحديد ما إذا كان الرسم البياني يحتوي على مجموعة مستقلة بحجم n. كل خوارزميات حل مشكلة المجموعة المستقلة تواجه تضخماً تركيبيًا، حيث ينمو عدد خطوات الحساب المطلوبة نمواً أسياً كدالة لحجم الرسم البياني. من ناحية أخرى، يمكن حل مسألة تحديد إذا ما كانت مجموعة معينة من الرؤوس مجموعة مستقلة في رسم بياني معين عن طريق المعاينة. هناك العديد من المسائل المنقسمة الى قسمين، حيث يصعب تحديد ما إذا كان تركيب معين موجودًا داخل عنصر إدخال (سؤال الوجود)، ولكن من السهل تحديد ما إذا كان مبنى معين هو من التركيب المطلوب (سؤال التحقق). 

من المعتقد عمومًا أن حل سؤال الوجود أصعب بكثير من حل سؤال التحقق لنفس المسألة. على سبيل المثال، من الصعب تحديد ما إذا كان من الممكن حل لغز الصور المتقطعة، ولكن من السهل التحقق من أن ترتيبًا معينًا لقطع اللغز يشكّل حلاً. وبشكل مماثل، يبدو من الصعب حل ألغاز سودوكو ولكن من السهل التحقق من صحة الحلول المعطاة. تقدم نظرية التعقيد تعريفات دقيقة لـ "P"، فئة جميع مسائل الوجود التي يسهل حلها، و"NP"، فئة مسائل الوجود التي يسهل التحقق من حلولها. إن الاعتقاد السائد بأن التحقق أسهل من الحل ذاته يشير بشكل مباشر إلى أن الفئة NP تتضمن الفئة P بأكملها، ولكن هذه النظرية لم تبرهن قط. إن مسألة ما إذا كان P = NP هي السؤال المفتوح الأكثر مركزية في علوم الكمبيوتر النظرية، وواحدة من أكثر الأسئلة المفتوحة شهرة في جميع مجالات الرياضيات. 

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

تنبع التقنية التي أوجدتُها من ورقة بحثية صدرت عام 1971 لستيفن كوك من جامعة تورنتو. أظهر كوك أن إحدى المسائل من فئة NP، وهي مسألة قابلية الإرضاء (المشار إليها بـ Sat) للمنطق القياسي هي NP-كاملة. وللقيام بذلك، أظهر أن أي مسألة من فئة NP يمكن اختزالها بكفاءة إلى Sat؛ أي أنه لكل مسألة A في NP، توجد خوارزمية فعالة تحول أي نموذج من A إلى نموذج مكافئ من Sat. ينبع من ذلك أنه إذا كان من السهل حل Sat، فإنه يمكن حل كل مسألة من فئة NP بسهولة. وتقريباً في نفس الفترة، برهن ليونيد ليفين من الاتحاد السوفييتي، الذي يعمل الآن بروفيسوراً في جامعة بوسطن، نتيجة مماثلة. 

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

إن الرأي السائد بين باحثي الجانب النظري للتعقيد هو أن P غير مساوٍ لـ NP، ولكن هذا الرأي غير منتشر على نطاق واسع. في الواقع لا يوجد أي برهان أو تفنيد في الأفق. لربما يجد شاب لامع النهج البديل الذي قد يحل مسألة P مقابل NP، بعد استلهامه من هذه المقالة. 

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