✖

أكبر مسألة في علوم الحاسوب: P مقابل NP

هناك سبع مسائل رياضية رآها معهد كلاي للرياضيات (Clay Mathematics Institute) صعبة ومثيرة للاهتمام إلى درجة أنه سمّاها مسائل جائزة الألفية، ويحصل من يحل أيّاً منها على جائزة قدرها مليون دولار. وإحدى هذه المسائل تتعلق بعلوم الحاسوب أيضاً، واسمها مسألة P مقابل NP. لنشرح إذن ما موضوع هذه المسألة.

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

المسألة 1: إيجاد أصغر عدد

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

نصف دقيقة؟ دقيقتين؟

هذه وحدات زمنية لا تهمنا كثيراً في علوم الحاسوب النظرية. فما يهمنا بالأحرى هو عدد العمليات. لذلك يمكننا أن نطرح السؤال بطريقة مختلفة قليلاً: كم ورقة يجب أن نفحص لنتأكد من أننا وجدنا أصغر عدد؟ والجواب أننا يجب أن نفحص كل الأوراق، لأنّ أصغر عدد قد يكون على الورقة الأخيرة. فإذا كانت أمامنا مئة ورقة، وجب أن نفحص مئة ورقة. وإذا كانت ألف ورقة، وجب أن نفحص ألف ورقة. وبوجه عام، إذا كانت أمامنا n ورقة، وجب أن نفحص n ورقة.

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

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

فهل توجد خوارزميات يكون فيها التحقق من النتيجة أسهل من إيجادها؟

المسألة 2: ناتج ضرب زوج من الأعداد

لنفترض الآن أنّ أمامنا كومتين متساويتين من الأوراق الصغيرة، وعلى كل ورقة عدد واحد أيضاً. والمطلوب أن نجد عدداً من الكومة A وعدداً من الكومة B بحيث يكون ناتج ضربهما العدد 918. فلتكن لدينا مثلاً كومتا الأعداد الآتيتان:

A={49,11,32,54,15}B={17,64,74,61,21}

كيف نجد زوجاً من الأعداد ناتج ضربهما 918؟ يمكننا ببساطة أن نجرّب كل الاحتمالات. فكم عددها؟ كثيرة نوعاً ما، فعددها 25. نبدأ بضرب العدد الأول من الكومة A، أي العدد 49، في كل عدد من الكومة B:

49×17=83349×64=313649×74=362649×61=298949×21=1029

لا يعطي أي زوج من هذه الأزواج العدد 918. فنجرّب الشيء نفسه مع بقية أعداد الكومة A، أي خمسة أزواج أخرى للعدد 11، وخمسة أزواج أخرى للعدد 32، وخمسة أزواج أخرى للعدد 54، وآخر خمسة أزواج للعدد 15. فنجرّب إذن 25 زوجاً من الأعداد إجمالاً. وفي النهاية نجد أنّ 54 × 17 = 918.

فما تعقيد هذه الخوارزمية؟ يهمنا عدد أزواج الأعداد التي اضطررنا إلى ضربها. كانت كل كومة تحتوي على خمس أوراق، واضطررنا إلى تجربة كل عدد من الأعداد الخمسة في الكومة الأولى مع كل عدد من الأعداد الخمسة في الكومة الثانية. فجرّبنا إجمالاً 5 × 5 = 25 توفيقاً. ولو كانت أمامنا كومتان في كل منهما 10 أوراق، لاضطررنا إلى تجربة 10 × 10 = 100 توفيق. وبالتعميم، إذا كانت أمامنا كومتان في كل منهما n ورقة، وجب أن نجرّب n · n = n2 توفيقاً.

نقول إنّ خوارزميتنا هذه تعقيدها n2، أي تعقيد تربيعي، لأنها توصف بدالة تربيعية.

لكن ما مدى صعوبة التحقق من النتيجة؟ إذا أجبنا بأنّ 54 و 17 هما العددان اللذان ناتج ضربهما 918، فلا يحتاج صديقنا إلى المرور على كل أزواج الأعداد من الكومتين كما فعلنا نحن. بل يكفيه أن يضرب هذا الزوج الواحد 54 × 17 ليعرف هل كلامنا صحيح أم لا. إذن يحتاج حل هذه المسألة إلى حساب ما يصل إلى n2 من نواتج الضرب، أما التحقق فيكفيه حساب ناتج ضرب واحد فقط. فتعقيد التحقق ثابت ويساوي 1.

وبهذا تختلف هذه المسألة اختلافاً كبيراً عن المسألة السابقة التي احتجنا فيها إلى عدد الخطوات نفسه للحساب وللتحقق بعده.

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

المسألة 3: مجموع المجموعة الجزئية

لننتقل إلى المسألة الثالثة. هذه المرة أمامنا اثنتا عشرة ورقة عليها أعداد، والمطلوب أن نجد أي عدد من الأوراق مجموع أعدادها صفر. فمثلاً:

A={24,−69,1,−15,−76,−60,16,−83,48,−22,54,−47}

المطلوب أن نختار من هذه الأعداد أي مجموعة أعداد مجموعها 0. فمثلاً الأعداد

24+48−69+1

مجموعها 4، ولذلك ليست إجابة صحيحة. والإجابة الصحيحة هي مجموعة الأعداد… حسناً، نترك إيجادها واجباً منزلياً 😉. فهناك مجموعة واحدة فقط من الأعداد مجموعها 0، ومن يبحث عنها يشعر بمدى صعوبة هذه المسألة.

نحتاج الآن إلى معرفة تعقيد هذه المسألة. وحسابه ليس بديهياً تماماً، وهو موجّه بالأحرى إلى عشّاق التفاصيل. فمن يهمه أن يعرف كيف يُحسب تعقيد هذه المسألة فليتابع القراءة، ويمكن لغيره الانتقال إلى الفقرة التالية. ⏩

كيف نجد إذن مجموعة أعداد مجموعها 0؟ يجب ببساطة أن نجرّب كل التوافيق الممكنة من الأعداد. فنجرّب كل الأزواج، وكل الثلاثيات، والرباعيات، والخماسيات، وهكذا، ونتحقق في كل مجموعة هل مجموعها صفر. فكم عدد هذه التوافيق؟

لنوضّح ذلك على مجموعة أصغر من الأعداد. كم مجموعة مختلفة من الأعداد، أي كم مجموعة جزئية، يمكن أن نكوّن من الأعداد الثلاثة B = {5, 7, 9}؟ عددها ثماني مجموعات:

B1={}B2={5}B3={7}B4={9}B5={5,9}B6={5,7}B7={7,9}B8={5,7,9}

نلاحظ أننا حسبنا أيضاً المجموعة الجزئية الخالية B1. وهي ليست مفيدة كثيراً الآن، لكننا أبقيناها لاكتمال القائمة. ولتبسيط الحساب نربط كل مجموعة جزئية بمتجه ثنائي. والمتجه الثنائي ببساطة متتالية من الأصفار والآحاد، مثل 00101010. وسنعمل بمتجهات ثنائية طولها ثلاثة. ونربط المتجه بالمجموعة الجزئية كما يلي: نربط 101 بالمجموعة الجزئية التي تحتوي على «العددين الأول والثالث من المجموعة الأصلية، دون العدد الثاني»، أي بالمجموعة {5, 9}. ونربط المتجه 110 بالمجموعة الجزئية التي تحتوي على «العددين الأول والثاني من المجموعة الأصلية، دون الثالث»، أي بالمجموعة {5, 7}، وهكذا.

B1={}→000B2={5}→100B3={7}→010B4={9}→001B5={5,9}→101B6={5,7}→110B7={7,9}→011B8={5,7,9}→111

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

يوجد متجهان ثنائيان طولهما واحد: 0 و 1.

ونحصل على المتجهات الثنائية التي طولها اثنان بأن نأخذ كل المتجهات الثنائية التي طولها واحد ونضيف 0 إلى نهاية كل منها، فنحصل على المتجهين 00 و 10. ثم نأخذ مرة أخرى كل المتجهات التي طولها 1 ونضيف إلى نهايتها 1، فنحصل على 01 و 11. وبذلك نحصل على كل المتجهات التي طولها 2: 00 و 01 و 10 و 11.

ونحصل على المتجهات الثنائية التي طولها ثلاثة بأن نأخذ كل المتجهات الثنائية التي طولها اثنان ونضيف إلى نهايتها صفراً: 000 و 010 و 100 و 110، ثم واحداً: 001 و 011 و 101 و 111.

وهكذا لكل طول تالٍ. نرى أننا إذا زدنا طول المتجه الثنائي بواحد، تضاعف عدد المتجهات الثنائية المختلفة. فللمتجه الذي طوله أربعة نحصل إذن على 2 × 2 × 2 × 2، أي على 16 توفيقاً مختلفاً.

وبوجه عام نستنتج أنه إذا كانت لدينا مجموعة M تحتوي على n عنصراً، فإنّ عدد كل المجموعات الجزئية للمجموعة M يساوي عدد كل المتجهات الثنائية المختلفة التي طولها n، وهو يساوي

2⋅2⋅…⋅2⏟n مرة=2n

2n أم n2: أليس الأمر سيّان؟ 🤷‍♂

إذن يوجد 2n من المجموعات الجزئية المختلفة التي يمكن تكوينها من مجموعة فيها n عدداً. وفي حالتنا لدينا n = 12 عدداً، ولذلك يجب أن نفحص 212 توفيقاً مختلفاً، أي 4096 توفيقاً. نقول إنّ هذه المسألة تعقيدها 2n، أي تعقيد أسي، لأنها توصف بالدالة الأسية.

نلاحظ أنّ تعقيد المسألة السابقة كان n2، أما تعقيد هذه المسألة فهو 2n. يبدو الأمران متشابهين جداً، أليس كذلك؟ لكنّ الفرق كبير بين أن يكون الأس ثابتاً وأن يكون الأس هو المتغير n. فعندما يكون n = 4 نحصل على

n2=42=162n=24=16

حسناً، حتى الآن النتيجتان متساويتان. وماذا لو كان n = 10؟

n2=102=1002n=210=1024

عجباً، لقد قفزت الدالة الأسية فجأة وأصبحت أكبر من الدالة التربيعية بنحو عشر مرات. وماذا نحصل عندما يكون n = 20؟

n2=202=4002n=220=1 048 576

عندما يكون n = 20 تكون قيمة التعقيد الأسي أكبر من قيمة التعقيد التربيعي بنحو 2,600 مرة. إذن نرى أنّ الدالة الأسية تنمو أسرع بكثير من الدالة التربيعية. ولنتذكر ذلك عندما يصيبنا وباء جديد ينتشر بين السكان بسرعة أسية.

فلو كانت أمامنا عشرون ورقة، لوجب أن نفحص 1,048,576 توفيقاً. وهذا عدد كبير نوعاً ما.

التحقق من صحة النتيجة

كم من الوقت يستغرق التحقق من أنّ مجموعة الأعداد الناتجة مجموعها 0 فعلاً؟ سيكون ذلك سريعاً نسبياً، فيكفي أن نجمع هذه المجموعة الواحدة من الأعداد. فإذا كان مجموعها 0 كانت مجموعة الأوراق صحيحة، وإذا كان المجموع مختلفاً كانت مجموعة الأوراق خاطئة.

ونرى مرة أخرى أنّ التحقق من النتيجة أسهل بكثير من إيجادها.

المسألة 4: مسألة البائع المتجول

مسألة البائع المتجول من أشهر المسائل الخوارزمية. وباختصار، لدينا بائع متجول يبيع المطر. وعلى هذا البائع أن يسافر كثيراً ليكسب رزقه. لذلك قرر أن يزور 14 مدينة عربية كبرى. ولأنه لا يريد أن يهدر شيئاً، قرر أن يجد أقصر طريق ممكن يمرّ به بكل هذه المدن. ومهمتنا أن نجد هذا الطريق الأقصر.

كيف نجد هذا الطريق الأقصر؟ نجرّب كل الاحتمالات.

ويمكننا أن نبسّط الأمر. لنفترض أنّ بين كل مدينتين طريقاً أقصر واحداً فقط. فكيف نجد أقصر طريق يمر بكل المدن؟ لدينا 14 مدينة، فلدينا إذن 14 احتمالاً لنقطة البداية. لنفرض أننا بدأنا من الدار البيضاء! فإلى أين يمكننا أن نذهب من الدار البيضاء؟ نظرياً يمكننا أن نذهب إلى أي مدينة أخرى، فنختار من بين 13 مدينة متبقية.

ويمكننا منذ الآن أن نحسب أنّ لدينا إجمالاً 14 × 13 طريقة لزيارة أول مدينتين، فلدينا 14 احتمالاً لنقطة البداية، ثم نختار من بين 13 مدينة متبقية.

وعندما نصل إلى المدينة الثانية يجب أن نتابع. لقد زرنا مدينتين، فيمكننا أن نسافر إلى واحدة من 12 مدينة متبقية. فيكون لدينا إجمالاً 14 × 13 × 12 طريقة لزيارة أول ثلاث مدن.

وعندما نزور المدينة الثالثة، يجب أن نختار واحدة من 11 مدينة متبقية، ثم واحدة من 10 مدن متبقية، وهكذا.

وعندما نزور كل المدن، نجد أنّ عدد الاحتمالات التي اخترنا منها إجمالاً هو

14×13×12×11×10×9×8×7×6×5×4×3×2×1

وهذا يذكّرنا بالمضروب الذي نرمز له بعلامة التعجب. فيمكننا أن نقول إنّ ناتج الضرب هذا يساوي 14!:

14!=14×13×12×11×10×9×8×7×6×5×4×3×2×1

إذن يوجد 14! طريقاً يمرّ بكل المدن الأربع عشرة. فهل هذا عدد كبير؟ نعم، كبير جداً، لأنّ

14!=87 178 291 200

وبوجه عام، لو بحثنا عن أقصر طريق بين n مدينة، لوجب أن نجرّب n! طريقاً مختلفاً. إذن تعقيد هذا الحل هو n!.

وكيف نتحقق من أننا وجدنا النتيجة الصحيحة؟ لو قال لنا أحد إنّ أقصر طريق يبدأ من تونس ويمرّ بالدار البيضاء ثم بعمّان، وهكذا، فكيف نتحقق من صحة كلامه؟ هذا صعب جداً 🤷‍♂. فعندما ننظر إلى هذا الطريق، لا نملك طريقة سهلة للتحقق من أنه هو الطريق الأقصر بالذات. بل يجب في الحقيقة أن نعيد الحساب كله من جديد. إذن تعقيد التحقق من النتيجة هو n! أيضاً.

الصنفان P و NP

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

المسألة تعقيد الحل تعقيد التحقق
أصغر عدد n n
ناتج ضرب زوج n2 1
مجموع المجموعة الجزئية 2n n
البائع المتجول n! n!

لنقسّم الآن مسائلنا إلى مجموعتين. المجموعة الأولى تتكوّن من المسائل السهلة الحل، وهي المسائل التي يمكن حلها بتعقيد n أو n2 أو n3 أو n4، وهكذا. وبما أننا نسمّي العبارات مثل n2 كثيرات حدود (polynomials)، فإننا نرمز لهذا الصنف من المسائل بالحرف P. فنقول إنّ الصنف P يحتوي على المسائل التي يمكن حلها في زمن كثير الحدود (أي أنّ تعقيدها مثلاً n2 أو n7). وهي بوجه عام المسائل التي يمكن حلها بسهولة إلى حد ما.

فتنتمي إلى الصنف P المسألة 1، إيجاد أصغر عدد، لأنّ تعقيد حلها n، وكذلك المسألة 2، ناتج ضرب زوج، لأنّ تعقيد حلها n2، وكلا التعقيدين كثير حدود.

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

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

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

مسألة P مقابل NP

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

فمثلاً نعلم أننا نستطيع أن نتحقق من نتيجة المسألة 3، مجموع المجموعة الجزئية، في زمن كثير الحدود. لكننا استخدمنا لحلها خوارزمية ليست كثيرة حدود، فتعقيد الخوارزمية المستخدمة أسي ويساوي 2n. فهل نعلم يقيناً أنه لا توجد لهذه المسألة أي خوارزمية تعقيدها كثير حدود؟

لا نعلم!

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

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

إذن مسألة P مقابل NP هي السؤال: هل الصنف P مطابق للصنف NP، أم أنهما صنفان مختلفان من المسائل؟

فإما أن يتحقق P = NP، وإما أن يتحقق P ≠ NP. ولا أحد يعرف الجواب، ومن يكتشفه تنتظره جائزة قدرها مليون دولار، ومجد خالد، وعلى الأرجح أيضاً جائزة تورينغ (Turing Award)، وهي بمنزلة جائزة نوبل لعلماء الحاسوب.

ماذا لو كان P = NP؟

ماذا سيحدث لو تحقق P = NP؟ ليس من السهل تماماً أن نقول ما الذي سيحدث. سنعرف أنّ لكل مسائل الصنف NP خوارزمية تحلها في زمن كثير الحدود، فنعرف مثلاً أنّ لمسألتنا 3، مجموع المجموعة الجزئية، خوارزمية تحلها في زمن كثير الحدود. لكنّ في ذلك ثلاثة أمور يجب الانتباه إليها:

  • معرفتنا بوجود هذه الخوارزمية لا تعني أننا نستطيع أن نجدها. فسنعرف ببساطة أنه توجد خوارزمية تحل المسألة في زمن كثير الحدود، لكننا قد لا نستطيع بناءها مئة سنة أخرى مثلاً. وهذا يشبه ما حدث عندما تنبأت النظرية النسبية العامة بوجود الثقوب السوداء، ومع ذلك استغرق الأمر عدة عقود أخرى قبل أن نتمكن من التقاط أول «صورة» لثقب أسود.
  • ووجود خوارزمية تعمل في زمن كثير الحدود لا يعني للأسف أنها سريعة. فقد نجد خوارزمية تعقيدها n100، فالعبارة n100 أيضاً كثيرة حدود. وإذا قارنّا بين التعقيدين 2n و n100، نجد أنّ الخوارزمية التي تعقيدها 2n تحتاج إلى عمليات أقل ما دام n صغيراً نسبياً. فمثلاً عندما يكون n = 20 يتحقق 220 = 1,048,576، في حين تعطي العبارة 20100 عدداً فيه نحو 130 رقماً، أي عدداً أكبر من 1,048,576 بنحو 120 منزلة. فتكون خوارزميتنا التي زمنها كثير الحدود في الواقع أبطأ من الخوارزمية الأسية، على الأقل ما دام n صغيراً نسبياً.
  • ولو استطعنا مع ذلك أن نجد خوارزمية سريعة تعمل في زمن كثير الحدود، لاستطعنا أن نحل كثيراً من المسائل بسرعة أكبر ودقة أعلى. وهذا بالطبع خبر إيجابي، لكنّ له أيضاً جوانبه السلبية. فهناك مجال يعتمد على أنّ بعض المسائل صعبة الحل، وهو علم التشفير. فقد يصبح كسر الشيفرات الحالية أسهل بكثير.

فاصل: مكافأةً لمن وصل في القراءة إلى هنا، نكشف أنّ حل المسألة 3 هو 24 + 1 − 60 + 16 − 83 + 48 + 54.

ماذا لو كان P ≠ NP؟

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

في الثقافة الشعبية

  • في إحدى حلقات مسلسل The Simpsons ينتقل هومر إلى واقع بديل غريب، فيظهر له أنّ P = NP. ويمكن مشاهدة ذلك على youtube.com.
  • أما في مسلسل Futurama فنرى في المستودع ملفين، أحدهما بعنوان P والآخر بعنوان NP. ويمكن مشاهدة ذلك على youtube.com.
  • والحلقة الثانية من الموسم الثاني من مسلسل Elementary، وعنوانها «Solve for X»، تناولت مقتل رياضي يُرجَّح أنه حلّ مسألة P مقابل NP.