هل P = NP ؟

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

هذا مثال على ما يطلق عليه علماء الحاسوب NP problem ، حيث إنه من السهل في حال سلمك زميلك في العمل قائمة ب100 طالب معرفة فيما إذا كانت مناسبة أم لا (أي لا تحوي أي زوج ظهر في قائمة العميد)، ولكن إن عملية توليد قائمة كهذه من الصفر صعبة جدا وغير عملية. في الواقع، فإن عدد الطرق الممكنة الكلي لاختيار 100 طالب من أصل 400 أكبر من عدد الذرات في الكون المعروف كاملا!

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

مشاكل مثل تلك المذكورة أعلاه هي بالتأكيد من هذا النوع NP، ولكن إلى الآن لم يستطع أحد أن يثبت أن هذه المشاكل بالصعوبة التي تبدو عليها، أي أنه فعلاً لا يوجد أية وسيلة ممكنة لتوليد حل مع مساعدة من جهاز كومبيوتر.

وقد تمت صياغة مشكلة P او NP بشكل مستقل من قبل ستيفن كوك وليونيد ليفين في عام 1971.

وبشكل عام، فإن المسائل من النوع P) P تعود إلىpolynomial time أي وقت حدودي) تدل على مجموعة من المشكلات الحسابية التي لها خوارزمية حل فعالة.

بينما المسائل من النوع NP) N تعود إلى nondeterministic أي غير حتمي) تدل على المسائل التي يسهل التحقق من صحة أحد الحلول لها ولكن ليس لها خوارزمية حل فعالة إلى الآن ومن الممكن ألا يوجد هكذا خوارزمية.

وإن مسألة P او NP ببساطة تسأل فيما إذا كان هذان النوعان من المسائل هو نفسه أي فيما إذا كان للمسائل من النوع NP خوارزمية حل فعالة لكن لم تكتشف بعد.

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

ومثال أوضح حتى هو لعبة سودوكو: مرة أخرى فإنها لعبة تمثل تحديا حقيقيا للحل، ولكن التحقق من صحة حل موجود هو فعل روتيني يخلو من أي متعة.

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

أما المشاكل التي تسمى "NP-complete" فهي ليست إلا حالات اختبار لمسألة P او NP: وفي حال إيجاد خوارزمية فعالة لأي منهم فإن لجميعهم خوارزميات فعالة (وبالتالي فإن إيجاد حل ليس أكثر صعوبة من التحقق من الحل).

ولكن في حال تم إثبات عدم وجود خوارزمية فعالة لحل إحدى هذه المسائل فإن P لا تساويNP (وبالتالي فإن عملية توليد حل حقا أصعب من عملية التحقق من صحة حل).

هنا بعض الأمثلة الكلاسيكية عن مسائل NP-complete:

مسألة التقسيم (معضلة السارقين “ النشاليَن” الفضائيين): على أرض كوكب فضائي، سارقان اثنان يقومان بسرقة محفظة. لتقاسم العائدات عليهما تقاسم المال بالتساوي: هل بإمكانهم ذلك؟ العملات الأرضية القياسية صممت لجعل مهمة كهذه سهلة، ولكن بشكل عام هذه مسألة من النوع NP-complete لأنه في حال وجود تقسيم متساوي للقطع النقدية، فإنه يمكن إثبات صحته بسهولة. (لكن العثور على هذا التقسيم هو الجزء الصعب!)

مسألة البائع المتجول: بائع متجول يتوجب عليه زيارة كل مدينة من ضمن مجموعة من المدن. لتوفير النفقات، البائع يريد إيجاد أقصر طريق يمر من جميع المدن. بفرض لدينا مسافة ما k ، فهل يوجد مسار يستطيع من خلاله أن يمر البائع بجميع المدن وطوله أصغر أو يساوي k ؟

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

ولكننا بالطبع سوف نستمر بالبحث!

المصادر:

هنا

هنا