اللغز الذي يساوي مليون دولار: ماذا تسأل نظرية P vs NP؟

تسأل نظرية P vs NP عمّا إذا كانت كل مشكلة يسهل التحقق من صحة حلها يسهل أيضاً إيجاد حلها. باختصار: هل المشاكل التي يسهل التحقق من حلها يسهل حلها أيضاً؟

لأنها إحدى مسائل الألفية السبع التي وضعها معهد كلاي للرياضيات، وكل واحدة منها مرصود لها جائزة بمليون دولار لمن يقدّم حلاً صحيحاً، وما زالت P vs NP بلا حل.

لو ثبت أن P تساوي NP لأصبحت مشاكل نعدّها صعبة اليوم، مثل كسر التشفير أو تحسين الخدمات اللوجستية، سهلة الحل، مما يغيّر وجه التشفير والأمن والحوسبة.