مقدمة في نظرية الحوسبة والتعقيد
نشرت: 2022-03-11هل تساءلت يومًا: ما هو بالضبط الجهاز الذي تقرأ عليه هذه المقالة؟ ما هو الحاسوب؟
يعود تاريخ العلوم الحاسوبية إلى فترة طويلة قبل أن يتم تخيل هذه الأجهزة الحاسوبية الحديثة. في صناعة تدور فيها الأسئلة الأكثر شيوعًا حول لغات البرمجة وأطر العمل والمكتبات ، غالبًا ما نأخذ في الاعتبار المفاهيم الأساسية التي تجعل الكمبيوتر علامة.
لكن أجهزة الكمبيوتر هذه ، التي يبدو أنها تمتلك إمكانات لا حصر لها - هل لديها أي قيود؟ هل توجد مشاكل لا يمكن استخدام أجهزة الكمبيوتر لحلها؟
في هذه المقالة ، سنتناول هذه الأسئلة من خلال الابتعاد عن تفاصيل لغات البرمجة وهياكل الكمبيوتر. من خلال فهم قوة وقيود أجهزة الكمبيوتر والخوارزميات ، يمكننا تحسين طريقة تفكيرنا وتحسين التفكير بشأن الاستراتيجيات المختلفة.
ينتج عن النظرة المجردة للحوسبة نتائج صمدت أمام اختبار الزمن ، وهي ذات قيمة لنا اليوم كما كانت عندما تم تطويرها في البداية في السبعينيات.
الحوسبة
ما هو الكمبيوتر؟ ما هي المشكلة؟
في المدرسة ، غالبًا ما يتم تعليمنا نموذجًا عقليًا للمشكلات والوظائف التي تسير على ما يلي:
الوظيفة هي إجراء تقوم بتطبيقه على إدخال x من أجل إيجاد مخرج f (x).
تبين أن التعريف الرياضي مختلف:
الوظيفة عبارة عن مجموعة من الأزواج المرتبة بحيث يكون العنصر الأول لكل زوج من مجموعة X (تسمى المجال) ، والعنصر الثاني لكل زوج من مجموعة Y (تسمى المجال أو النطاق) ، وكل عنصر من المجال مقترن بالضبط بعنصر واحد من النطاق.
كان هذا تماما الفم. لكن، تحديدا ماذا يعني ذلك؟
يخبرنا هذا التعريف أن الكمبيوتر هو آلة لوظائف الحوسبة.
لماذا ا؟
لأن أجهزة الكمبيوتر تحول المدخلات التعسفية إلى بعض المخرجات. وبعبارة أخرى ، فإنهم يحلون المشاكل. يتطابق التعريفان للوظائف ، الذي نعرفه جيدًا والآخر الرسمي ، في العديد من الأغراض العملية.
ومع ذلك ، فإن التعريف الرياضي يسمح لنا بالتوصل إلى استنتاجات مثيرة للاهتمام مثل وجود وظائف غير قابلة للحساب (على سبيل المثال ، مشاكل غير قابلة للحل):
لأنه لا يمكن وصف كل وظيفة على أنها خوارزمية.
قواعد اللعبة
للمساعدة في صنع حججنا ، دعونا نتخيل أجهزة الكمبيوتر كآلات تأخذ بعض المدخلات ، وتنفذ سلسلة من العمليات ، وبعد مرور بعض الوقت ، تعطي بعض المخرجات.
سوف نسمي الإدخال أبجدية الآلة ؛ أي ، مجموعة من سلاسل الأحرف من مجموعة محدودة. على سبيل المثال ، قد تكون الأبجدية للجهاز ثنائية (0 و 1) أو قد تكون مجموعة أحرف ASCII. أي تسلسل محدد للأحرف هو سلسلة — على سبيل المثال ، "0110".
علاوة على ذلك ، سنقوم بتمثيل مخرجات الجهاز كقرار ثنائي للقبول والرفض ، يتم تسليمه بمجرد انتهاء الجهاز (على أمل) من حسابه. يتناسب هذا التجريد جيدًا مع التعريف الرياضي للوظائف من وقت سابق.
بالنظر إلى هذه المعلمات ، من المهم تحديد نوع آخر: مجموعة من السلاسل النصية. ربما نهتم بمجموعة الخيوط التي تقبلها آلة ما ، أو ربما نبني آلة تقبل الخيوط في مجموعة معينة دون غيرها ، أو ربما نسأل عما إذا كان من الممكن حتى تصميم آلة تقبل كل شيء في بعض مجموعة معينة وليس غيرها.
في جميع هذه الحالات ، تسمى مجموعة السلاسل لغة - على سبيل المثال ، مجموعة كل السلاسل الثنائية التي تمثل الأرقام الزوجية أو مجموعة السلاسل التي تحتوي على عدد زوجي من الأحرف. اتضح أن اللغات ، مثل الأرقام ، يمكن تشغيلها باستخدام عوامل تشغيل مثل التسلسل ، والاتحاد ، والتقاطع ، وما شابه ذلك.
أحد العوامل المهمة هو مشغل Kleene star الذي يستخدم أيضًا مع التعبيرات العادية. يمكن اعتبار هذا اتحادًا لكل السلطات الممكنة للغة. على سبيل المثال ، إذا كانت لغتنا أ هي مجموعة السلاسل {'01'، '1'} ، فإن أحد أعضاء A * هو السلسلة "0101111".
العد
الجزء الأخير من اللغز قبل أن نثبت ادعائنا بأنه ليست كل الوظائف قابلة للحساب هو مفهوم العد. حدسيًا ، سيُظهر إثباتنا أن هناك المزيد من اللغات ؛ وهذا يعني أن المشاكل أكثر من البرامج الممكنة لحلها. يعمل هذا لأن مسألة ما إذا كانت سلسلة ما تنتمي إلى لغة (نعم / لا) هي نفسها مشكلة.
بتعبير أدق ، يدعي دليلنا أن مجموعة البرامج الممكنة لا حصر لها إلى حد كبير في حين أن مجموعة اللغات فوق الأبجدية لا حصر لها بلا حدود.
في هذه المرحلة ، قد تفكر ، "اللانهاية فكرة غريبة بما يكفي بحد ذاتها ؛ الآن علي أن أتعامل مع اثنين منهم! "
حسنًا ، الأمر ليس بهذا السوء. المجموعة اللانهائية هي التي يمكن تعدادها. من الممكن أن نقول أن هذا هو العنصر الأول ، وهذا هو العنصر الثاني ، وهكذا دواليك ، وفي النهاية يتم تخصيص رقم لكل عنصر من عناصر المجموعة. خذ مجموعة الأرقام الزوجية ، على سبيل المثال. يمكننا القول أن 2 هي الأولى ، 4 الثانية ، 6 الثالثة ، وهكذا. هذه المجموعات لا حصر لها أو قابلة للعد.
مع بعض المجموعات ، مثل الأرقام الحقيقية ، لا يهم كم أنت ذكي ؛ ببساطة لا يوجد تعداد. هذه المجموعات لا حصر لها أو غير معدودة.
عدد كبير من البرامج
أولاً ، نريد أن نظهر أن مجموعة برامج الكمبيوتر قابلة للعد. لأغراضنا ، نقوم بذلك من خلال ملاحظة أن مجموعة كل السلاسل على أبجدية محدودة قابلة للعد. هذا يعمل لأن برامج الكمبيوتر هي في حد ذاتها سلاسل محدودة.
الدليل واضح ، ولا نغطي التفاصيل هنا. الخلاصة الأساسية هي أن هناك العديد من برامج الكمبيوتر بقدر ما توجد ، على سبيل المثال ، أرقام طبيعية.
أن أكرر:
مجموعة كل السلاسل فوق أي أبجدية (على سبيل المثال ، مجموعة من كافة برامج الكمبيوتر) قابلة للعد.
العديد من اللغات لا تعد ولا تحصى
بالنظر إلى هذا الاستنتاج ، ماذا عن المجموعات الفرعية لهذه الأوتار؟ سئل بطريقة أخرى ماذا عن مجموعة كل اللغات؟ اتضح أن هذه المجموعة غير معدودة.
مجموعة كل اللغات فوق أي أبجدية غير معدودة.
مرة أخرى ، لا نغطي الدليل هنا.
الآثار
على الرغم من أنها قد لا تكون واضحة على الفور ، إلا أن عواقب عدم إمكانية عد اللغات وإمكانية عد مجموعة جميع برامج الكمبيوتر عميقة.
لماذا ا؟
افترض أن A هي مجموعة أحرف ASCII ؛ أحرف ASCII هي فقط تلك اللازمة لإنشاء برنامج كمبيوتر. يمكننا أن نرى أن مجموعة السلاسل التي تمثل ، على سبيل المثال ، برامج JavaScript ، هي مجموعة فرعية من A * (هنا ، * هو مشغل Kleene star). يعتبر اختيار JavaScript اختيارًا تعسفيًا. نظرًا لأن هذه المجموعة من البرامج هي مجموعة فرعية من مجموعة معدودة ، فلدينا مجموعة برامج JavaScript قابلة للعد.
بالإضافة إلى ذلك ، دعونا نعتبر أنه بالنسبة لأي لغة L ، يمكننا تحديد بعض الدالة f التي تقدر بـ 1 إذا كانت بعض السلاسل x في L و 0 بخلاف ذلك. كل هذه الوظائف متميزة. نظرًا لوجود تطابق 1: 1 مع مجموعة جميع اللغات ولأن مجموعة جميع اللغات غير معدودة ، فلدينا مجموعة من كل هذه الوظائف غير معدودة.
هذه هي النقطة العميقة:
نظرًا لأن مجموعة جميع البرامج الصالحة قابلة للعد ولكن مجموعة الوظائف ليست كذلك ، فلا بد من وجود بعض الوظائف التي لا يمكننا ببساطة كتابة برامج لها.
لا نعرف حتى الآن كيف تبدو هذه الوظائف أو المشاكل ، لكننا نعلم أنها موجودة. هذا إدراك متواضع ، لأن هناك بعض المشاكل التي لا يوجد حل لها. نحن نعتبر أجهزة الكمبيوتر قوية للغاية وقادرة ، ومع ذلك فإن بعض الأشياء بعيدة عن متناولها.
الآن يصبح السؤال ، "كيف تبدو هذه المشاكل؟" قبل أن نواصل وصف مثل هذه المشكلات ، يتعين علينا أولاً وضع نموذج للحسابات بطريقة عامة.
آلات تورينج
طور آلان تورينج أحد النماذج الرياضية الأولى للكمبيوتر. هذا النموذج ، المسمى بآلة تورينج ، هو جهاز بسيط للغاية يلتقط تمامًا مفهومنا عن الحوسبة.
الإدخال إلى الجهاز عبارة عن شريط تمت كتابة الإدخال عليه. باستخدام رأس القراءة / الكتابة ، يقوم الجهاز بتحويل الإدخال إلى إخراج من خلال سلسلة من الخطوات. في كل خطوة ، يتم اتخاذ قرار بشأن ما إذا كنت تريد الكتابة على الشريط وما إذا كنت تريد تحريكه يمينًا أم يسارًا. يعتمد هذا القرار على شيئين بالضبط:
الرمز الحالي تحت الرأس ، و
الحالة الداخلية للجهاز ، والتي يتم تحديثها أيضًا عند كتابة الرمز
هذا هو.
عالمية
في عام 1926 ، لم يطور آلان تورينج آلة تورينج فحسب ، بل كان لديه أيضًا عدد من الأفكار الرئيسية الأخرى حول طبيعة الحساب عندما كتب مقالته الشهيرة ، "حول الأرقام القابلة للحساب". لقد أدرك أن برنامج الكمبيوتر نفسه يمكن اعتباره مدخلاً لجهاز الكمبيوتر. من خلال وجهة النظر هذه ، كانت لديه فكرة جميلة مفادها أن آلة تورينج يمكنها محاكاة أو تنفيذ هذا الإدخال.
بينما نأخذ هذه الأفكار كأمر مسلم به اليوم ، في أيام تورينج ، كانت فكرة مثل هذه الآلة العالمية بمثابة اختراق كبير سمح لتورنج بتطوير مشاكل غير قابلة للحل.
رسالة الكنيسة تورينج
قبل أن نواصل ، دعنا نفحص نقطة مهمة: نحن نعلم أن آلة تورينج هي نموذج للحساب ، لكن هل هي عامة بما فيه الكفاية؟ للإجابة على هذا السؤال ، ننتقل إلى أطروحة Church-Turing التي تؤكد البيان التالي:
كل شيء يمكن حسابه يمكن حسابه بواسطة آلة تورينج.
بينما طور تورينج آلة تورينج كنموذج للحساب ، طور ألونزو تشيرش أيضًا نموذجًا للحساب يُعرف باسم lambda-calculus. هذه النماذج قوية ، لأن كلاهما يصف الحساب ويفعل ذلك بطريقة مساوية لأي من أجهزة الكمبيوتر الحالية أو لأي كمبيوتر على الإطلاق. هذا يعني أنه يمكننا استخدام آلة Turing لوصف المشكلات غير القابلة للحل التي نسعى إليها ، مع العلم أن نتائجنا ستنطبق على جميع أجهزة الكمبيوتر المحتملة في الماضي والحاضر وما بعده.
التعرف والحكم
علينا أن نغطي خلفية أكثر قليلاً قبل أن نصف بشكل ملموس مشكلة غير قابلة للحل ، وهي مفاهيم أدوات التعرف على اللغة ومقرري اللغة.
يمكن التعرف على اللغة إذا كانت هناك آلة تورينج تتعرف عليها.
و
يمكن تحديد اللغة إذا كانت هناك آلة تورينج تقررها.
لكي تكون متعرفًا على اللغة ، يجب أن تقبل آلة تورينج كل سلسلة في اللغة ويجب ألا تقبل أي شيء بخلاف اللغة. قد يرفض أو يتكرر على مثل هذه السلاسل. لكي تكون مُقررًا ، يجب أن تتوقف آلة Turing دائمًا عند إدخالها إما عن طريق القبول أو الرفض.
هنا ، فكرة التوقف عن المدخلات أمر بالغ الأهمية. في الواقع ، نرى أن أصحاب القرار أقوى من المتعرفين. علاوة على ذلك ، فإن المشكلة قابلة للحل ، أو بمعنى آخر ، فإن الوظيفة لا يمكن تحديدها إلا إذا كانت هناك آلة تورينج تحدد اللغة الموصوفة بواسطة الوظيفة.
عدم القدرة على اتخاذ القرار
إذا كنت قد كتبت برنامج كمبيوتر من قبل ، فمن المؤكد أنك يجب أن تعرف الشعور بالجلوس هناك فقط وأنت تشاهد الكمبيوتر وهو يدور بعجلاته عند تنفيذ البرنامج. أنت لا تعرف ما إذا كان البرنامج يستغرق وقتًا طويلاً فقط أو إذا كان هناك خطأ ما في الكود يتسبب في حلقة لا نهائية. ربما تساءلت عن سبب عدم قيام المترجم بالتحقق من الكود لمعرفة ما إذا كان سيتوقف أو يتكرر إلى الأبد عند التشغيل.
لا يمتلك المترجم مثل هذا الفحص لأنه ببساطة لا يمكن إجراؤه. لا يعني ذلك أن مهندسي المترجم ليسوا أذكياء بما يكفي أو يفتقرون إلى الموارد ؛ من المستحيل ببساطة التحقق من برنامج كمبيوتر عشوائي لتحديد ما إذا كان يتوقف.
يمكننا إثبات ذلك باستخدام آلة تورينج. يمكن وصف آلات تورينج بأنها أوتار ، لذلك يوجد عدد لا يحصى منها. افترض أن M 1 و M 2 وما إلى ذلك يشكلون مجموعة جميع آلات Turing. دعونا نحدد الوظيفة التالية:
هنا ، <M> هي صيغة "تشفير السلسلة لـ M" ، وتمثل هذه الوظيفة مشكلة إخراج 1 إذا توقف M i بقبول M j كمدخل وإخراج 0 بخلاف ذلك. لاحظ أنه يجب على M i التوقف (أي أن يكون صاحب قرار). هذا مطلوب لأننا نرغب في وصف وظيفة غير قابلة للتقرير (أي مشكلة غير قابلة للحل).
الآن ، دعونا أيضًا نحدد اللغة L التي تتكون من ترميزات سلسلة لآلات تورينج التي لا تقبل الأوصاف الخاصة بها:
على سبيل المثال ، قد تقوم بعض الأجهزة M 1 بإخراج 0 على الإدخال <M 1 > بينما قد تقوم آلة أخرى M 2 بإخراج 1 على الإدخال <M 2 >. لإثبات أن هذه اللغة غير قابلة للتقرير ، نسأل ما يفعله M L ، الجهاز الذي يقرر اللغة L ، عندما يُعطى وصفه الخاص به <M L > كمدخل. هناك احتمالان:
يقبل M L <M L >
أو
يرفض M L <M L >
إذا قبلت M L التشفير الخاص بها ، فهذا يعني أن <M L > ليس في اللغة L ؛ ومع ذلك ، إذا كان الأمر كذلك ، فلا ينبغي أن تقبل M L تشفيرها في المقام الأول. من ناحية أخرى ، إذا لم تقبل M L التشفير الخاص بها ، فعندئذٍ يكون <M L > في اللغة L ، لذلك كان من المفترض أن تقبل M L تشفير السلسلة الخاص بها.
في كلتا الحالتين ، لدينا مفارقة ، أو من الناحية الرياضية ، تناقض ، يثبت أن اللغة L غير قابلة للتقرير ؛ وهكذا ، وصفنا أول مشكلة غير قابلة للحل.
وقف المشكلة
في حين أن المشكلة التي وصفناها للتو قد لا تبدو ذات صلة ، يمكن اختزالها إلى مشاكل إضافية غير قابلة للحل ذات أهمية عملية ، وعلى الأخص مشكلة التوقف:
لغة ترميزات آلات تورينج التي تتوقف عند الوتر الفارغ.
تنطبق مشكلة التوقف على السؤال عن سبب عدم تمكن المترجمين من اكتشاف الحلقات اللانهائية من وقت سابق. إذا لم نتمكن من تحديد ما إذا كان البرنامج سينتهي على السلسلة الفارغة ، فكيف يمكننا تحديد ما إذا كان تنفيذه سيؤدي إلى حلقة لا نهائية؟
في هذه المرحلة ، قد يبدو أننا لوّحنا بأيدينا للتو للوصول إلى استنتاج بسيط ؛ ومع ذلك ، فقد أدركنا بالفعل أنه لا توجد آلة تورينج يمكنها معرفة ما إذا كان برنامج الكمبيوتر سيتوقف أو يظل في حلقة إلى الأبد. هذه مشكلة مهمة في التطبيقات العملية ، ولا يمكن حلها على آلة تورينج أو أي نوع آخر من أجهزة الكمبيوتر. لا يمكن لـ iPhone حل هذه المشكلة. لا يمكن لسطح المكتب الذي يحتوي على العديد من النوى حل هذه المشكلة. السحابة لا تستطيع حل هذه المشكلة. حتى لو ابتكر شخص ما جهاز كمبيوتر كمي ، فلن يكون قادرًا على حل مشكلة التوقف.
ملخص
في فحصنا لنظرية الحوسبة ، رأينا كيف أن هناك العديد من الوظائف التي لا يمكن حسابها بأي معنى عادي للكلمة من خلال حجة العد. لقد حددنا بدقة ما نعنيه بالحساب ، ونعود إلى إلهام تورينج من تجربته الخاصة مع القلم والورق لإضفاء الطابع الرسمي على آلة تورينج. لقد رأينا كيف يمكن لهذا النموذج أن يحسب أي شيء يستطيع أي كمبيوتر اليوم أو يتخيله للغد أن يحسب ، وأدركنا فئة من المشاكل غير القابلة للحساب على الإطلاق.
ومع ذلك ، فإن الحوسبة لها جانب سلبي. فقط لأننا نستطيع حل مشكلة لا يعني أنه يمكننا حلها بسرعة. بعد كل شيء ، ما فائدة الكمبيوتر إذا كانت حساباته لن تنتهي قبل أن تنطفئ الشمس علينا عشرات الملايين من السنين في المستقبل؟
ترك الوظائف واللغات القابلة للحساب وراءنا ، نناقش الآن تعقيد الحساب ، ومسح الحسابات الفعالة ومشكلة P مقابل NP الشهيرة.
تعقيد
بطيء مقابل سريع
يتعرف علماء الكمبيوتر على مجموعة متنوعة من فئات المشكلات ، وهناك فئتان نهتم بهما تتضمن المشكلات التي يمكن لأجهزة الكمبيوتر حلها بسرعة أو بكفاءة والمعروفة باسم P والمشكلات التي يمكن التحقق من حلولها بسرعة ولكن لا يمكن الحصول عليها بسرعة والمعروفة باسم NP .
على سبيل المثال ، لنفترض أنك مسؤول عن تطوير خوارزميات لخدمة المواعدة عبر الإنترنت وطرح شخص ما السؤال ، "هل يمكن للجميع الحصول على موعد؟" تتلخص الإجابة في إقران الأفراد المتوافقين بحيث يتم إقران الجميع. تبين أن هناك خوارزميات فعالة لحل هذه المشكلة. هذه المشكلة موجودة في المجموعة P.
حسنًا ، ماذا لو أردنا تحديد أكبر زمرة بين مستخدمينا؟ بالزمرة ، نعني أكبر شبكة من الأفراد تتوافق جميعها مع بعضها البعض. عندما يكون عدد المستخدمين منخفضًا ، يمكن حل هذه المشكلة بسرعة. يمكننا بسهولة تحديد ، على سبيل المثال ، زمرة بها 3 مستخدمين. ومع ذلك ، عندما نبدأ في البحث عن مجموعات أكبر ، يصبح حل المشكلة أكثر صعوبة. هذه المشكلة في NP مجموعة.
التعريفات الرسمية
P هي مجموعة المسائل التي يمكن حلها في زمن كثير الحدود. أي أن عدد الخطوات الحسابية مقيد بدالة متعددة الحدود فيما يتعلق بحجم المشكلة. نحن نعلم أن السؤال "هل يمكن للجميع الحصول على موعد؟" السؤال ، المعروف أيضًا باسم مشكلة المطابقة الثنائية ، موجود في P.
NP هي مجموعة المشاكل التي يمكن التحقق منها في زمن كثير الحدود. وهذا يشمل كل مشكلة في P ، بالطبع ؛ ومع ذلك ، لا نعرف ما إذا كان هذا الاحتواء صارمًا. نحن على علم بالمشكلات التي يمكن التحقق منها بكفاءة ولكن لا يمكن حلها بكفاءة ، لكننا لا نعرف ما إذا كانت المشكلة مستعصية على الحل حقًا. مشكلة الزمرة هي واحدة من هذه المشاكل. نعلم أنه يمكننا التحقق من الحل بكفاءة ، لكننا لا نعرف على وجه اليقين ما إذا كان بإمكاننا حل المشكلة بكفاءة.
أخيرًا ، NP-complete هي مجموعة المشكلات التي تعد أصعب المشكلات في NP . يشار إليهم على أنهم الأصعب لأن أي مشكلة في NP يمكن تحويلها بكفاءة إلى NPC . نتيجة لذلك ، إذا كان على شخص ما تحديد حل فعال لمشكلة ما في NPC ، فسيتم استيعاب فئة NP بأكملها بواسطة P. مشكلة الزمرة هي أيضا في المجلس الوطني لنواب الشعب .
وهكذا ، نصل إلى مشكلة P مقابل NP . يعتقد العديد من علماء الكمبيوتر وعلماء الرياضيات بقوة أن P و NP ليسا متساويين. إذا كانت كذلك ، فإن الآثار ستكون أبعد من العمق. تعتمد الكثير من البنية التحتية الرقمية اليوم على حقيقة أن هناك مشاكل في NP ليست في P. إذا لم يكن الأمر كذلك ، فإن أساليب التشفير ، على سبيل المثال ، ستنهار بين عشية وضحاها ، مما يسمح للشخص الذي يمتلك حلاً فعالاً لمشكلة NPC بتخريب حتى أكثر بروتوكولات الأمان صرامة.
دقة التتبع
بالنسبة للمبتدئين في علوم الكمبيوتر ، قد لا يبدو الفرق بين مشاكل المطابقة والزمرة مشكلة كبيرة. في الواقع ، يمكن أن يكون الفرق بين مشكلة في P ومشكلة في NP دقيقًا للغاية. القدرة على معرفة الفرق أمر مهم لأي شخص يصمم الخوارزميات في العالم الحقيقي.
تأمل مشكلة أقصر طريق. بالنظر إلى موقعين ، الهدف هو تحديد أقصر طريق بينهما. يقوم جهاز iPhone بحساب هذا في غضون أجزاء من الثانية. هذه مشكلة حسابية يمكن تتبعها.
من ناحية أخرى ، ضع في اعتبارك مشكلة البائع المتجول ، حيث يكون الهدف هو زيارة مجموعة فرعية من الوجهات المحتملة التي تنتهي عند الأصل أثناء السفر لأقصر مسافة ممكنة. هذه المشكلة مشابهة لمشكلة أقصر طريق لكنها NP كاملة ؛ كما يشرح سبب كون لوجستيات سلسلة التوريد صناعة بمليارات الدولارات.
يمكننا في الواقع أن نكون أكثر دقة. بدلاً من طلب أقصر طريق (P) ، يمكننا أن نطلب أطول مسار بدون دورات. تبين أن مشكلة المسار الأطول هي أيضًا NP كاملة.
هناك العديد من الأمثلة على هذا التمييز الدقيق ، بما في ذلك تحديد أغلفة الرؤوس في الرسوم البيانية ثنائية الجزء مقابل الرسوم البيانية العامة أو إرضاء الصيغ المنطقية مع اثنين مقابل ثلاثة حرفي لكل جملة. النقطة المهمة هي أنه ليس من الواضح على الفور ما إذا كانت المشكلة في P أو NP ، وهذا هو السبب في أن تحليل الوقت يعد مهارة حاسمة. إذا كانت الخوارزمية التي يجب على المرء تصميمها تتعلق بمشكلة في P ، فإننا نعلم أن هناك حلًا فعالاً. من ناحية أخرى ، إذا كانت المشكلة في NP ، فلدينا حجة قوية للدفاع عنها ضد السعي إلى حل ، لأن الخوارزمية ، بشكل عام ، ستستغرق وقتًا طويلاً لحل المشكلة.
ملخص
في فحص التعقيد هذا ، حددنا فئات المشاكل P و NP. يمثل P بشكل غير رسمي المشكلات التي يمكن حلها بكفاءة بواسطة الكمبيوتر بينما يمثل NP المشكلات التي يمكن التحقق منها بكفاءة.
لم يتمكن أحد من إثبات أن P لا تساوي NP. ما إذا كانت هاتان الفئتان من المشاكل متكافئتان أم لا تعرف بمشكلة P مقابل NP ، وهي أهم مشكلة مفتوحة في علوم الكمبيوتر النظرية اليوم إن لم يكن في جميع الرياضيات. في الواقع ، في عام 2000 ، أطلق معهد Clay Math Institute على مشكلة P مقابل NP كأحد أهم سبعة أسئلة مفتوحة في الرياضيات وقدم مكافأة قدرها مليون دولار لإثبات يحدد حل هذه المشكلة.
خاتمة
في هذه المقالة ، بحثنا في مجالات الحوسبة والتعقيد ، ونجيب على أسئلة كبيرة مثل ، "ما هو الكمبيوتر؟" في حين أن التفاصيل قد تكون ساحقة ، إلا أن هناك عددًا من الوجبات السريعة العميقة التي تستحق التذكر:
هناك بعض الأشياء التي لا يمكن حسابها ببساطة ، مثل مشكلة التوقف.
هناك بعض الأشياء التي لا يمكن حسابها بكفاءة ، مثل المشاكل في NPC.
الأهم من التفاصيل هي طرق التفكير في المسائل الحسابية والحسابية. في حياتنا المهنية وحتى في يومنا هذا ، قد نواجه مشاكل لم نشهدها من قبل ، ويمكننا استخدام أدوات وتقنيات مجربة وحقيقية لتحديد أفضل مسار للعمل.
مزيد من القراءة على مدونة Toptal Engineering:
- كيفية الاقتراب من كتابة المترجم الفوري من الصفر