ما هي معضلة علم التشفير التي تقارب جائزة حلها المليون دولار؟

معضلة P مقابل NP

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

لنقل أنه يمكنك التحقق من الجواب بسهولة، لكن هل الأمر بسهولة الحل نفسه؟

هذه هي معضلة P مقابل NP، معضلة بجائزة مليون دولار لمن يستطيع حلها إذا قدم برهانًا صحيحًا.

ما معضلة P مقابل NP؟

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

«الزمن متعدد الحدود: حالة تكون فيها المسألة قابلة للحل في خطوات تُقاس بواسطة عامل متعدد الحدود، نظرًا إلى تعقيد المدخلات».

لنفترض أن التعقيد في المدخلات هو عدد ما وليكن (n)، فإن خوارزميات الزمن متعدد الحدود ستتمكن من حل المسألة في عدد من الخطوات يساوي n مرفوعًا للأس k.

تطرح معضلة P مقابل NP تساؤلًا: هل المسائل التي يمكن التحقق من حلولها في الزمن متعدد الحدود، حُلّت أيضًا في الزمن متعدد الحدود؟

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

بعض هذه المسائل تضم الألعاب، مثل السفينة الحربية، ومكعب روبيك NxNxN. تضم أيضًا أسئلةً نظرية مشهورة، مثل مسألة البائع المتجول. إذا وجدنًا حلولًا لهذه المسائل، فيمكن إيجاد حل عام لمشكلات NP الكاملة.