المجموعات

P مقابل NP و NP-Complete وخوارزمية لكل شيء

P مقابل NP و NP-Complete وخوارزمية لكل شيء

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

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

مشاكل التصنيف: P Vs NP

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

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

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

ذات صلة: 7 خوارزميات أساسية تدير العالم

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

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

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

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

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

NP-Hard و NP- كامل

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

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

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

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

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

الخوارزمية لكل شيء

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

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

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

المقالة الأخيرة في سلسلتنا حول الخوارزميات والحساب ، خوارزميات الكم ومستقبل الحوسبة ما بعد الكلاسيكية، يمكن العثور عليها هنا


شاهد الفيديو: كليكبانك إلى عن على مبتدئين: كيف إلى يصنع مال على كليكبانك إلى عن على مجانا جديد الدورة التعليمية (ديسمبر 2021).