مسألة المليون دولار P = NP

مسألة المليون دولار P = NP  وجحيم التعقيد الحسابي

تعتبر الرياضيات لغة شاملة للكون، فكل ما حولنا يمكن تفسيره رياضيا، فالرياضيات هي المنطق الذي يتفق عليه جميع البشر بل و يمكن ان تحاور مخلوقا لم تره من قبل فقط باستخدام الأرقام.

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

لكن هل تساءلت يوما إلى أي مدى يمكن للرياضيات أن تكون معقدة؟ وهل توجد مسائل رياضية لم يتمكن العلماء من حلها إلى اليوم؟

في يوم 24 مايو 2000 قام معهد كلاي للرياضيات بتحديد سبعة مسائل عجز العلماء عن حلها لسنين عديدة وقام بوضع جائزة قدرها مليون دولار لمن يتمكن من حل أي واحدة من هذه المسائل السبعة. فلنتابع معا إحدى هذه المسائل وهي مسألة P=NP  فقد تتمكن أنت من حلها.

تعتبر هذه الحدسية هي الأسهل بين مسائل الألفية السبعة من حيث وصفها وتفسيرها فهي لا تتطلب مفاهيم رياضية معقدة لكن وجود حل لها ليس سهلا بالتأكيد. يمكن اعتبار هذه الحدسية هي الحد الفاصل بين الرياضيات وعلوم الكمبيوتر النظرية فهي تخص مدى سرعة حل الخوارزميات.

المسائل ذات الصنف P

إذا أعطيتك مجموعة أعداد غير مرتبة و قلت لك أخرج لي أصغر رقم من هذه المجموعة فستبدأ بقراءة الأعداد وتدوّن أصغر رقم تقابله وتواصل القراءة إلى ان تجد رقما أصغر من الذي دونته فتكتب هذا الرقم الجديد بدل القديم تواصل هكذا إلى أن تنتهي المجموعة. فإذا أعطيتك مثلا عشرين عددا فستقرأ كل عدد مرة واحدة و بذلك يستغرق حل هذه المسألة عشرين خطوة بمعدل قراءة واحدة لكل عدد. أي أن عدد الخطوات مساو لعدد العناصر.

الآن تخيل أنني أعطيتك هذه الأعداد وطلبت منك أن ترتّبها من الأصغر إلى الأكبر، ستستغرق خطوات أكثر وبذلك وقتا أطول. فمثلا إذا كانت هذه الأعداد 10 أعداد فيتطلب حلها 50 خطوة  وإذا كانت 20 عددا فيتطلب حلها 200 خطوة. أي أن عدد خطوات حل مسألة الترتيب مناسب نصف لمربع عدد العناصر. فإذا كان عدد العناصر n فإن عدد خطوات حل المسألة هو (n×n/2).

هتين المسألتين تنتميان إلى المسائل من صنف P من Polynomial أي أن عدد خطوات حلها (أو ما يسمى بتعقيدها) مناسب ل n مرفوعا ل a (مع العلم ان a هو أي عدد طبيعي و n هو عدد عناصر المسألة: في هذا المثال، n يمثّل عدد الأعداد و a يمثل 2). 

المسائل ذات الصنف NP

لنأخذ على سبيل المثال لعبة السودوكو، قد تستغرق ساعات في حلها لكن التأكد إن كان الحل صحيحا أو خاطئا لن يخذ منك عدة دقائق. فمسألة السودوكو لا تنتمي الى المسائل ذات الصنف P. 

الآن تخيل أنك دخلت متجر أدوات وعندك حقيبة ظهريمكن أن تحمل وزنا لا يتجاوز 40 كيلوغراما، و طلبت منك زوجتك أن تختارعدة أغراض لوضعا في الحقيبة وأن قيمة هذه الأغراض التي ستأخذها يجب أن لا تقل عن 5000 دولار وأن يكون وزنها جميعا لا يتجاوز 40 كغ طبعا. 

ستبدأ بتجربة وضع الأغراض داخل الحقيبة إلى أن تصل إلى مجموعة الأغراض المناسبة أي التي يقل وزنها مجتمعة عن 40 كغ و يتجاوز ثمنها 5000 دولار. 

هل تعلم كم عدد الخطوات التي ستتخذها لتجربة كل الاحتمالات الممكنة؟ انه مساو ل 2 مرفوعا ل n) n هو عدد الأغراض التي ستجرّبها). 

فإذا كان عدد الأغراض 10 فأمامك 1024 احتمالا واذا كان 100 فعدد الإحتمالات يتجاوز 12 × 10^30 احتمالا و إذا كان عدد الأغراض في المتجر 300 فعدد الإحتمالات الممكنة يتجاوز عدد الذرات الموجودة في الكون المرئي.

بصفة عامة إذا كان تعقيد مسألة ما مناسبا ل(a مرفوعا ل n) (مع العلم ان a هو عدد اكبر من 1 و n هو عدد العناصر) ويسهل التحقق من حلها فإن هذه المسألة تنتمي للصنف NP أو (non-determinstic polynomial).

لكن توجد مسائل أكثر تعقيدا مثل مسائل NP الصعبة و مسائل NP الكاملة.

• مسائل NP الصعبة هي مسائل ليس بالضرورة يمكننا التحقق من حلها أي قد لا تكون تنتمي للمسائل NP، لكن إذا وجدت خوارزمية لحلها فإن هذه الخوارزمية تستطيع حل اي مسألة NP أخرى.

• مسائل NP الكاملة هي مسائل تنتمي الى صنف NP و NP الصعبة في نفس الوقت.

تنويه :
المسائل من النوع P يسهل أيضا التحقق من صحتها ويمكن اعتبارها مجموعة صغيرة داخل مجموعة NP. هذا في حالة إذا ما كان P و NP مختلفتين.

نص حدسية  P = NP

هل يمكن بطريقة ما ايجاد تبسيط لمسائل ذات الصنف NP لتصبح من الصنف P؟

إذا استطاع أحد أن يثبت أن كل المسائل من نوع NP يمكن / أو لا يمكن أن تتحول بطريقة ما إلى مسائل من نوع P فسيكون قد تمكن من حل هذه المعضلة.

إذا أردت ان تثبت أن P غير مساوية ل NP فيكفي أن تأخذ أي مسألة تنتمي للصنف NP و تبرهن بطريقة ما أنه من غيرالممكن حلها في وقت من نوع (Polynomial). أما اذا أردت أن تثبت أن P=NP فيجب ان تأخذ أي مسألة من مسائل NP الكاملة و تبرهن أنه يمكن حلها في وقت من نوع (Polynomial) ومن هذه المسائل : مسألة حقيبة الظهر، مسألة البائع المتجول، المسألة SAT ...

إن إيجاد حل رياضي للمسألة المليونية P = NP يمكن أن يحدث ثورة في مجال عالم الحواسيب والكمبيوتر. فأنظمة التشفير الإلكتروني تعتمد على استعمال الأعداد الأولية. وإذا تمكن أحد من إثبات أن P=NP باستعمال معادلات رياضية فسيستطيع تفكيك أي عدد إلى مجموعة أعداد أولية مهما كان هذا العدد كبيرا و بذلك سيتمكن من فك تشفير أكثر الأنظمة أمانا.