دروس الحوسبة السريعة

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

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

ما هي الصعوبة الأساسية للمهمة؟ هذه هي صياغة المهمة الأساسية لعلماء الكمبيوتر الذين يحاولون فرز المهام وفقًا لما يسمى. دروس الصعوبة . هذه هي المجموعات التي تحتوي على جميع المهام الحسابية التي لا تتطلب أكثر من كمية ثابتة من الموارد الحسابية - مثل الوقت أو الذاكرة. لنأخذ مثالاً بسيطًا برقم كبير مثل 123 456 789 001. يمكن للمرء أن يسأل: هل هو رقم أولي - واحد يقسم فقط على 1 ونفسه؟ يمكن لعلماء الكمبيوتر الإجابة عليه باستخدام خوارزميات سريعة - بحيث لا يبدأون في التباطؤ في الأعداد الكبيرة العشوائية. في حالتنا ، اتضح أن هذا الرقم ليس أوليًا. ثم يمكننا أن نسأل السؤال: ما هي عواملها الرئيسية؟ ولكن لا توجد خوارزمية سريعة للإجابة عنها - فقط إذا كنت تستخدم جهاز كمبيوتر كمومي. لذلك ، يعتقد علماء الكمبيوتر أن هاتين المهمتين تنتميان إلى فئات التعقيد المختلفة.

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

لا يمكن أن يكون الفرق بين الطبقات بالكاد واضحًا أو واضحًا ، ومن الصعب جدًا فهم جميع الفئات جيدًا. لذلك ، قمنا بتجميع هذا الدليل لسبع فئات الصعوبة الأساسية. ونعم ، لن تخلط بين BPP و BQP.

ص

يدل على : وقت كثير الحدود

وصف قصير : جميع المهام التي يمكن للكمبيوتر الكلاسيكي (غير الكم) حلها بسهولة.

الوصف الدقيق : يجب أن تتوقف خوارزميات الفئة P عن العمل وتعطي الإجابة الصحيحة ليس أكثر من الوقت n ^c ، حيث n هو طول بيانات الإدخال ، c ثابت.

المهام النموذجية :

• هو الرقم الأولي؟
• ما هو أقصر مسار بين نقطتين؟

ما الذي يريد الباحثون معرفته : هل P يتزامن مع NP؟ سوف تحدث المصادفة ثورة في علوم الكمبيوتر وتجعل معظم أنظمة التشفير لا معنى لها (ولكن لا أحد يصدق ذلك تقريبًا).

NP

يدل على : الوقت متعدد الحدود غير القطعي

وصف قصير : جميع المهام التي يمكن للكمبيوتر الكلاسيكي التحقق منها بسهولة إذا كان هناك حل.

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

المهام النموذجية :

• مهمة النقر . تخيل رسمًا بيانيًا بحواف ورؤوس - على سبيل المثال ، تشير القمم إلى مستخدمي الشبكة الاجتماعية ، وتشير الحافة إلى أنهم "أصدقاء". الزمرة هي مجموعة فرعية من هذا الرسم البياني حيث يكون جميع الناس أصدقاء لبعضهم البعض. يمكنك طرح الأسئلة التالية حول الرسم البياني: هل يوجد نقرة بها 20 شخصًا؟ 50 شخصا؟ 100؟ العثور على زمرة هي مهمة NP كاملة ، أي أن تعقيدها هو الأعلى من بين جميع مهام NP. ولكن الحصول على إجابة محتملة - مجموعة فرعية من 50 عقدة قد تكون أو لا تكون نقرة - من السهل التحقق منها.
• مهمة البائع . بالنظر إلى مجموعة من المدن بمسافات بين أي زوجين - هل هناك طريقة للتجول في جميع المدن ، والقيادة أقل من مسافة معينة؟ على سبيل المثال ، هل يمكن لبائع أن يسافر جميع العواصم الأمريكية التي تقل عن 11000 ميل؟

ما يريد الباحثون معرفته: P = NP؟ متخصصون في علوم الكمبيوتر ولم يقتربوا من حل هذه المشكلة.

PH

يدل على : التسلسل الهرمي متعدد الحدود

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

الوصف الدقيق : يحتوي PH على مهام مع عدد من "محددات الكمية" المختلفة التي تعقد هذه المهام. مثال لمشكلة مع مُحددات كمية مختلفة: إذا تم إعطاؤنا X ، فهل هناك Y بحيث أنه لكل Z يوجد W الذي R راض عنه؟ كلما زادت كمية المحددات في المشكلة ، كلما كانت أكثر تعقيدًا ، وكلما زاد التسلسل الهرمي متعدد الحدود.

تتمثل المهمة النموذجية في تحديد ما إذا كانت هناك نقرة بحجم 50 حقًا ، ولا توجد نقرة بحجم 51.

ما يريد الباحثون معرفته : لم يتمكن أحد من إثبات أن PH مختلف عن P. هذه المشكلة تعادل المساواة بين P و NP ، لأنه إذا تبين فجأة أن P = NP ، فسيتم تخفيض جميع PH إلى P (P = PH).

PSPACE

يدل على : ضيق الفضاء متعدد الحدود

وصف قصير : يحتوي PSPACE على جميع المهام التي يمكن حلها باستخدام قدر معقول من الذاكرة.

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

المهمة النموذجية : يتم تضمين جميع المهام من P و NP و PH في PSPACE.

ما الذي يريد الباحثون معرفته : هل يختلف PSPACE عن P؟

بكب

يدل على : الوقت متعدد الحدود الكمومي مع تحديد احتمال الخطأ

وصف قصير : جميع المهام التي يمكن حلها بسهولة على جهاز كمبيوتر الكم.

الوصف الدقيق : جميع المهام التي يمكن حلها على جهاز كمبيوتر كمومي في وقت كثير الحدود.

مشكلة نموذجية : أوجد العوامل الأولية لعدد صحيح.

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

EXPTIME

يدل على الوقت الأسي

وصف قصير : جميع المهام التي يمكن حلها في الوقت الأسي على جهاز كمبيوتر كلاسيكي.

الوصف الدقيق : يحتوي EXP على جميع الفئات السابقة - P و NP و PH و PSPACE و BQP. أثبت الباحثون أنه مختلف عن P - اكتشفوا المهام التي هي جزء من EXP وليست جزءًا من P.

المهمة النموذجية : تعميم الألعاب مثل الشطرنج والشيكرز. إذا كانت لوحة الشطرنج يمكن أن تكون بأي حجم ، فإن مهمة تحديد ما إذا كان أحد اللاعبين لديه ميزة تصبح مهمة EXP.

ما يريد الباحثون معرفته : يريدون أن يثبتوا أن PSPACE لا يحتوي على EXP. يعتقدون أن هناك مهام جزء من EXP ولكنها ليست جزءًا من PSPACE ، لأنه في بعض الأحيان يستغرق الأمر وقتًا طويلاً لحل مهمة من EXP. يعرف الباحثون كيفية فصل EXP و P.

BPP

يدل على : الوقت متعدد الحدود مع تحديد احتمال الخطأ

وصف قصير : المهام التي يمكن حلها بسرعة باستخدام الخوارزميات التي تستخدم العشوائية.

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

المهمة النموذجية : لديك صيغتان مختلفتان تعطيان كثيرات الحدود مع العديد من المتغيرات. هل تحسب هذه الصيغ نفس كثير الحدود؟ هذه هي مهمة التحقق من الهوية متعددة الحدود.

ما يرغب الباحثون في معرفته : هل BPP و P. متساويان. إذا كانا متساويين ، فيمكن إزالة أي خوارزمية ذات عشوائية من العشوائية. إنهم يعتقدون أنه - لكل مشكلة لها خوارزمية عشوائية فعالة ، هناك خوارزمية حتمية فعالة - لكنهم لم يتمكنوا بعد من إثبات ذلك.