مشكلة P مقابل NP

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 27 صور
الموسوعة الحرة
مشكلة لم تُحل في علوم الحاسوب
إذا كان من الممكن التحقق من حل مشكلة ما في وقت متعدد الحدود، فهل يجب أن تكون المشكلة قابلة للحل في وقت متعدد الحدود؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

تُعدّ مسألة P مقابل NP مشكلة رئيسية لم تُحلّ بعد في علوم الحاسوب النظرية . وبصورة غير رسمية، تتساءل هذه المسألة عما إذا كان بالإمكان حلّ كل مشكلة يمكن التحقق من حلّها بسرعة بسرعة أيضاً.

هنا، تعني كلمة "بسرعة" وجود خوارزمية تحل المهمة وتعمل في زمن متعدد الحدود (على عكس الزمن الأسي مثلاً )، أي أن زمن إنجاز المهمة محدود بدالة متعددة الحدود تعتمد على حجم مُدخلات الخوارزمية. الفئة العامة من الأسئلة التي يمكن لخوارزمية ما الإجابة عنها في زمن متعدد الحدود هي " P " أو "الفئة P". بالنسبة لبعض الأسئلة، لا توجد طريقة معروفة لإيجاد إجابة بسرعة، ولكن إذا توفرت الإجابة، يمكن التحقق منها بسرعة. فئة الأسئلة التي يمكن التحقق من إجابتها في زمن متعدد الحدود هي " NP "، اختصارًا لـ "زمن متعدد الحدود غير الحتمي". [ ملاحظة 1 ] [ 1 ]

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

تُعتبر هذه المسألة أهم مسألة مفتوحة في علوم الحاسوب . [ 2 ] فضلًا عن كونها مسألةً بالغة الأهمية في نظرية الحوسبة ، فإنّ أي برهان، سواءً كان صحيحًا أم خاطئًا، سيكون له آثار عميقة على الرياضيات، وعلم التشفير ، وبحوث الخوارزميات، والذكاء الاصطناعي ، ونظرية الألعاب ، ومعالجة الوسائط المتعددة، والفلسفة ، والاقتصاد ، والعديد من المجالات الأخرى. [ 3 ] وهي إحدى مسائل جائزة الألفية السبع التي اختارها معهد كلاي للرياضيات ، والتي تبلغ قيمة جائزة كل منها مليون دولار أمريكي لأول حل صحيح.

مثال

ضع في اعتبارك مشكلة نعم/لا التالية: معطى شبكة سودوكو غير مكتملة بحجمن2×ن2{\displaystyle n^{2}\times n^{2}}هل يوجد على الأقل حل قانوني واحد حيث يكون كل صف وعمود ون×ن{\displaystyle n\times n}المربع يحتوي على الأعداد الصحيحة من 1 إلىن2{\displaystyle n^{2}}من السهل التحقق من صحة إجابات "نعم" في مسألة سودوكو المعممة هذه عند وجود حل مرشح. مع ذلك، لا يُعرف ما إذا كانت هناك خوارزمية تعمل في زمن متعدد الحدود قادرة على الإجابة بـ"نعم" أو "لا" بشكل صحيح على جميع حالات هذه المسألة. لذا، فإن سودوكو المعممة تندرج ضمن فئة NP (قابلة للتحقق السريع)، ولكنها قد تندرج أو لا تندرج ضمن فئة P (قابلة للحل السريع). (من الضروري النظر في نسخة معممة من سودوكو، لأن أي سودوكو ذات حجم ثابت لا تحتوي إلا على عدد محدود من الشبكات الممكنة. في هذه الحالة، تندرج المسألة ضمن فئة P، حيث يمكن إيجاد الحل بالرجوع إلى جدول).

تاريخ

تم تقديم البيان الدقيق لمشكلة P مقابل NP في عام 1971 بواسطة ستيفن كوك في ورقته البحثية الرائدة "تعقيد إجراءات إثبات النظرية"، [ 4 ] وبشكل مستقل بواسطة ليونيد ليفين في عام 1973. [ 5 ]

على الرغم من أن مشكلة P مقابل NP قد عُرّفت رسميًا في عام 1971، إلا أن هناك إشارات سابقة إلى المشكلات الكامنة وراءها. ففي عام 1955، كتب عالم الرياضيات جون ناش رسالة إلى وكالة الأمن القومي ، متوقعًا أن الوقت اللازم لفك شفرة معقدة بما فيه الكفاية سيزداد أُسّيًا مع طول المفتاح. [ 6 ] إذا ثبت ذلك، [ ملاحظة 2 ] فسيؤدي هذا إلى ما يُعرف الآن بـ P  ≠  NP، حيث يمكن التحقق من المفتاح المقترح في وقت متعدد الحدود. وفي رسالة كتبها كورت غودل إلى جون فون نيومان عام 1956، تساءل غودل عما إذا كان من الممكن حل مسألة إثبات النظريات (المعروفة الآن بأنها مسألة كاملة مشتركة من فئة NP ) في وقت تربيعي أو خطي ، وافترض أنه إذا كان الأمر كذلك، فإنه يمكن أتمتة اكتشاف البراهين الرياضية. [ 7 ]

سياق

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

في هذا النوع من التحليل، يلزم وجود نموذج للحاسوب الذي يجب تحليل الزمن فيه. وعادةً ما تفترض هذه النماذج أن الحاسوب حتمي (بالنظر إلى حالة الحاسوب الحالية وأي مدخلات، لا يوجد سوى إجراء واحد ممكن يمكن أن يتخذه الحاسوب) ومتسلسل (ينفذ الإجراءات واحداً تلو الآخر).

في هذه النظرية، تتألف الفئة P من جميع مسائل القرار (المُعرّفة أدناه ) القابلة للحل على آلة تسلسلية حتمية في زمن متعدد الحدود بالنسبة لحجم المُدخلات؛ وتتألف الفئة NP من جميع مسائل القرار التي يمكن التحقق من حلولها الإيجابية في زمن متعدد الحدود عند توفر المعلومات الصحيحة، أو بعبارة أخرى، التي يمكن إيجاد حلولها في زمن متعدد الحدود على آلة غير حتمية . [ 8 ] من الواضح أن P ⊆ NP. ولعلّ أكبر سؤال مفتوح في علوم الحاسوب النظرية يتعلق بالعلاقة بين هاتين الفئتين.

هل P تساوي NP؟

منذ عام 2001، أجرى ويليام غاسارش  ثلاثة استطلاعات رأي للباحثين حول مسألة P ≠  NP والمسائل ذات الصلة. [ 9 ] [ 10 ] [ 11 ] بلغت نسبة المجيبين الذين يعتقدون أن P  ≠  NP 61% في عام 2001، [ ملاحظة 3 ] و83% في عام 2011، و88% في عام 2018، وذلك بناءً على 100 و151 و124 إجابة على التوالي. [ 11 ] وعند حصر الاستطلاع على الخبراء، اعتقد 99% من المجيبين في عام 2018 أن P  ≠  NP. [ 11 ] لا تُشير هذه الاستطلاعات إلى ما إذا كانت P  =  NP أم لا؛ كما ذكر غاسارش: "هذا لا يُقرّبنا من حلّ مسألة P = ؟NP أو من معرفة متى سيتم حلّها، ولكنه يُحاول أن يكون تقريرًا موضوعيًا عن الرأي السائد في هذا العصر." [ 9 ]

اكتمال NP

مخطط أويلر لمجموعة مسائل P و NP و NP-complete و NP-hard (باستثناء اللغة الفارغة ومكملها، والتي تنتمي إلى P ولكنها ليست NP-complete)

للإجابة على سؤال P  =  NP، يُعدّ مفهوم اكتمال NP مفيدًا للغاية. تُعرَّف مسائل NP-الكاملة بأنها مسائل يُمكن اختزال أي مسألة NP أخرى إليها في وقت متعدد الحدود، ويظل حلها قابلاً للتحقق في وقت متعدد الحدود أيضًا. أي أنه يُمكن تحويل أي مسألة NP إلى أي مسألة NP-كاملة. بعبارة أخرى، مسألة NP-الكاملة هي مسألة NP لا تقل صعوبة عن أي مسألة أخرى في NP.

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

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

من التعريف وحده، يبدو وجود مسائل NP-كاملة غير بديهي؛ ومع ذلك، يمكن صياغة مسألة NP-كاملة بسيطة على النحو التالي: بالنظر إلى آلة تورينج M مضمونة التوقف في وقت متعدد الحدود، هل يوجد مدخل بحجم متعدد الحدود تقبله M ؟ [ 12 ] تقع هذه المسألة في فئة NP لأنه (بالنظر إلى مدخل معين) من السهل التحقق مما إذا كانت M تقبل المدخل عن طريق محاكاة M ؛ وهي مسألة NP-كاملة لأنه يمكن ترميز أداة التحقق لأي حالة معينة من مسألة في فئة NP كآلة M تعمل في وقت متعدد الحدود وتأخذ الحل المراد التحقق منه كمدخل. عندئذٍ، يتم تحديد ما إذا كانت الحالة "نعم" أم "لا" بناءً على وجود مدخل صالح.

كانت مسألة إرضاء المسائل المنطقية البوليانية، والمعروفة أيضًا باسم SAT، أول مسألة طبيعية ثبت أنها من فئة NP-كاملة. وكما ذُكر سابقًا، فإن هذه المسألة هي نظرية كوك-ليفين؛ ويتضمن برهانها على أن إرضاء المسائل المنطقية البوليانية من فئة NP-كاملة تفاصيل تقنية حول آلات تورينج وعلاقتها بتعريف NP. مع ذلك، بعد إثبات أن هذه المسألة من فئة NP-كاملة، وفر البرهان بالاختزال طريقة أبسط لإظهار أن العديد من المسائل الأخرى هي أيضًا من فئة NP-كاملة، بما في ذلك لعبة سودوكو التي نوقشت سابقًا. في هذه الحالة، يُظهر البرهان أن حل سودوكو في زمن متعدد الحدود يمكن استخدامه أيضًا لإكمال المربعات اللاتينية في زمن متعدد الحدود. [ 13 ] وهذا بدوره يُعطي حلًا لمسألة تقسيم الرسوم البيانية ثلاثية الأجزاء إلى مثلثات، [ 14 ] والتي يمكن استخدامها بعد ذلك لإيجاد حلول للحالة الخاصة من SAT المعروفة باسم 3-SAT، [ 15 ] والتي بدورها تُقدم حلًا لإرضاء المسائل المنطقية البوليانية بشكل عام. لذا، فإن حل سودوكو في زمن متعدد الحدود يؤدي، عبر سلسلة من التحويلات الميكانيكية، إلى حل قابلية الإرضاء في زمن متعدد الحدود، والذي بدوره يمكن استخدامه لحل أي مسألة NP أخرى في زمن متعدد الحدود. وباستخدام تحويلات كهذه، يمكن اختزال فئة واسعة من المسائل التي تبدو غير مترابطة إلى بعضها البعض، وهي في جوهرها "المسألة نفسها".

مشاكل أكثر صعوبة

على الرغم من عدم معرفة ما إذا كانت P  =  NP، إلا أن هناك مسائل معروفة خارج نطاق P. وكما يُعرَّف الصنف P بدلالة زمن التشغيل متعدد الحدود، فإن الصنف EXPTIME هو مجموعة جميع مسائل القرار التي لها زمن تشغيل أُسّي . بعبارة أخرى، يمكن حل أي مسألة في EXPTIME بواسطة آلة تورينج حتمية في زمن O (2p ( n ) ) ، حيث p ( n ) دالة متعددة الحدود لـ n . تُعتبر مسألة القرار كاملة في EXPTIME إذا كانت ضمن هذا الصنف، ولكل مسألة في EXPTIME اختزال متعدد الحدود إليها. من المعروف أن عددًا من المسائل كاملة في EXPTIME. ولأنه يمكن إثبات أن P  ≠  EXPTIME، فإن هذه المسائل تقع خارج نطاق P، وبالتالي تتطلب زمنًا أطول من متعدد الحدود. في الواقع، وفقًا لنظرية التسلسل الهرمي الزمني ، لا يمكن حلها في زمن أقل بكثير من الزمن الأُسّي. وتشمل الأمثلة إيجاد استراتيجية مثالية لمواقع الشطرنج على رقعة N × N [ 16 ] ومشاكل مماثلة لألعاب لوحية أخرى. [ 17 ]

تتطلب مشكلة تحديد صحة عبارة في حساب بريسبرغر وقتًا أطول. أثبت فيشر ورابين في عام 1974 [ 18 ] أن كل خوارزمية تحدد صحة عبارات بريسبرغر ذات الطول n يكون وقت تشغيلها على الأقل22جن{\displaystyle 2^{2^{cn}}}لبعض الثوابت c . لذا، من المعروف أن هذه المسألة تتطلب وقت تشغيل يتجاوز الوقت الأسي. بل إن المسائل غير القابلة للحسم ، مثل مسألة التوقف، أكثر صعوبة . لا يمكن حلها بالكامل بواسطة أي خوارزمية، بمعنى أنه بالنسبة لأي خوارزمية معينة، يوجد على الأقل مُدخل واحد لن تُنتج الخوارزمية الإجابة الصحيحة له؛ إما أن تُنتج إجابة خاطئة، أو تنتهي دون تقديم إجابة قاطعة، أو تستمر في العمل إلى ما لا نهاية دون إنتاج أي إجابة على الإطلاق.

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

مشاكل في فئة NP غير معروفة بأنها في فئة P أو NP-كاملة

في عام ١٩٧٥، أثبت ريتشارد إي. لادنر أنه إذا كانت P  ≠  NP، فإنه توجد مسائل في NP ليست ضمن P ولا NP-كاملة. [ ٢٠ ] تُسمى هذه المسائل بالمسائل الوسيطة NP. تُعد مسألة تماثل الرسوم البيانية ، ومسألة اللوغاريتم المتقطع ، ومسألة تحليل الأعداد الصحيحة إلى عواملها الأولية أمثلة على مسائل يُعتقد أنها وسيطة NP. وهي من بين المسائل القليلة جدًا في NP التي لا يُعرف أنها تنتمي إلى P أو أنها NP-كاملة.

تُعرف مسألة تماثل الرسوم البيانية بأنها المسألة الحسابية التي تُعنى بتحديد ما إذا كان رسمان بيانيان محدودان متماثلين . ومن المسائل المهمة التي لم تُحل بعد في نظرية التعقيد، تحديد ما إذا كانت مسألة تماثل الرسوم البيانية تندرج ضمن فئة P، أو NP-كاملة، أو NP-متوسطة. الإجابة غير معروفة، ولكن يُعتقد أن المسألة على الأقل ليست NP-كاملة. [ 21 ] إذا كانت مسألة تماثل الرسوم البيانية NP-كاملة، فإن التسلسل الهرمي ذي الوقت متعدد الحدود ينهار إلى مستواه الثاني. [ 22 ] ونظرًا للاعتقاد السائد بأن التسلسل الهرمي متعدد الحدود لا ينهار إلى أي مستوى محدود، يُعتقد أن مسألة تماثل الرسوم البيانية ليست NP-كاملة. أفضل خوارزمية لحل هذه المسألة، والتي وضعها لازلو باباي ، تعمل في وقت شبه متعدد الحدود . [ 23 ]

مشكلة تحليل الأعداد الصحيحة إلى عواملها الأولية هي مشكلة حسابية تتمثل في تحديد التحليل إلى العوامل الأولية لعدد صحيح مُعطى. وبصياغة أخرى، هي مشكلة اتخاذ قرار، أي تحديد ما إذا كان للمُدخل عامل أقل من k . لا توجد خوارزمية فعالة معروفة لتحليل الأعداد الصحيحة إلى عواملها الأولية، وهذه الحقيقة تُشكل أساس العديد من أنظمة التشفير الحديثة، مثل خوارزمية RSA . تندرج مشكلة تحليل الأعداد الصحيحة إلى عواملها الأولية ضمن فئة NP و co-NP (وحتى ضمن UP و co-UP [ 24 ] ). إذا كانت المشكلة كاملة من فئة NP، فإن التسلسل الهرمي للوقت متعدد الحدود سينهار إلى مستواه الأول (أي NP = co-NP). أكثر الخوارزميات المعروفة كفاءة لتحليل الأعداد الصحيحة إلى عواملها الأولية هي غربال حقل الأعداد العام ، والذي يستغرق وقتًا متوقعًا قدره

يا(خبرة⁡((64ن9سجل⁡(2))13(سجل⁡(نسجل⁡(2)))23)){\displaystyle O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)}

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

مقارنة P بالمسائل "السهلة"

يُظهر الرسم البياني العلاقة بين زمن التشغيل وحجم المسألة لمسألة حقيبة الظهر باستخدام خوارزمية متخصصة حديثة. ويشير التوافق التربيعي إلى أن التعقيد الخوارزمي للمسألة هو O((log( n )) ² ). [ 25 ]

افترضت جميع المناقشات السابقة أن P تعني "سهل" و"ليس ضمن P" تعني "صعب"، وهو افتراض يُعرف باسم فرضية كوبام . وهو افتراض شائع في نظرية التعقيد، ولكن توجد بعض المحاذير.

أولًا، قد يكون هذا غير صحيح عمليًا. قد تحتوي خوارزمية متعددة الحدود نظرية على عوامل ثابتة أو أسس كبيرة للغاية، مما يجعلها غير عملية. على سبيل المثال، يمكن حل مشكلة تحديد ما إذا كان الرسم البياني G يحتوي على H كعنصر فرعي ، حيث H ثابت، في زمن تشغيل قدره O ( n² ) ، [ 26 ] حيث n هو عدد رؤوس G. ومع ذلك، فإن ترميز O الكبير يخفي ثابتًا يعتمد بشكل كبير جدًا على H. هذا الثابت أكبر من2↑ ↑(2↑ ↑(2↑ ↑(ح/2))){\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2))))}(باستخدام تدوين السهم لأعلى لكنوث )، وحيث h هو عدد الرؤوس في H. [ 27 ]

من جهة أخرى، حتى لو ثبت أن مسألة ما هي مسألة NP-كاملة، وحتى لو كانت P  ≠  NP، فقد تظل هناك طرق فعالة لحلها عمليًا. توجد خوارزميات للعديد من مسائل NP-الكاملة، مثل مسألة حقيبة الظهر ، ومسألة البائع المتجول ، ومسألة قابلية الإرضاء البولياني ، والتي يمكنها حل العديد من الحالات الواقعية بشكل أمثل في وقت معقول. يمكن أن يكون متوسط ​​التعقيد التجريبي (الوقت مقابل حجم المسألة) لهذه الخوارزميات منخفضًا بشكل مدهش. ومن الأمثلة على ذلك خوارزمية سيمبلكس في البرمجة الخطية ، والتي تعمل بشكل جيد للغاية عمليًا؛ فعلى الرغم من أن تعقيدها الزمني في أسوأ الحالات يكون أسيًا ، إلا أنها تعمل على قدم المساواة مع أفضل الخوارزميات المعروفة ذات الوقت متعدد الحدود. [ 28 ]

وأخيرًا، هناك أنواع من العمليات الحسابية التي لا تتوافق مع نموذج آلة تورينج الذي يتم تعريف P و NP عليه، مثل الحوسبة الكمومية والخوارزميات العشوائية .

أسباب تدعو للاعتقاد بأن P ≠ NP أو P = NP

يُعيد كوك صياغة المشكلة في كتابه "مشكلة P مقابل NP" على النحو التالي: "هل P  =  NP؟" [ 29 ]. ووفقًا لاستطلاعات الرأي [ 9 ] [ 30 ]، يعتقد معظم علماء الحاسوب أن P  ≠  NP. أحد الأسباب الرئيسية لهذا الاعتقاد هو أنه بعد عقود من دراسة هذه المشكلات، لم يتمكن أحد من إيجاد خوارزمية ذات زمن متعدد الحدود لأي من أكثر من 3000 مشكلة مهمة معروفة من فئة NP-كاملة (انظر قائمة المشكلات NP-كاملة ). وقد تم البحث عن هذه الخوارزميات قبل وقت طويل من تعريف مفهوم اكتمال NP (كانت مشكلات كارب الـ 21 من بين أوائل المشكلات التي تم اكتشافها، وكانت جميعها مشكلات معروفة وقت إثبات اكتمالها). علاوة على ذلك، فإن النتيجة P  =  NP ستؤدي إلى العديد من النتائج الأخرى المثيرة للدهشة التي يُعتقد حاليًا أنها خاطئة، مثل NP  = co-NP و P = PH .   

ويُجادل أيضاً بشكل بديهي بأن وجود مشاكل يصعب حلها ولكن يسهل التحقق من حلولها يتوافق مع تجربة العالم الحقيقي. [ 31 ]

إذا كانت P = NP، فسيكون العالم مكانًا مختلفًا تمامًا عما نتصوره عادةً. لن تكون هناك قيمة خاصة لـ"القفزات الإبداعية"، ولن تكون هناك فجوة جوهرية بين حل المشكلة والتعرف على الحل بمجرد إيجاده.

من جهة أخرى، يعتقد بعض الباحثين أن الاعتقاد بأن P  ≠  NP هو ثقة مفرطة، وأنه ينبغي على الباحثين أيضاً استكشاف براهين P  =  NP. على سبيل المثال، في عام 2002، صدرت هذه التصريحات: [ 9 ]

الحجة الرئيسية المؤيدة لفرضية أن P  ≠  NP هي غياب أي تقدم جوهري في مجال البحث الشامل. وهذه، في رأيي، حجة ضعيفة للغاية. فمجال الخوارزميات واسع جدًا، وما زلنا في بداية استكشافه. [...] كما يُظهر حل نظرية فيرما الأخيرة أن أبسط المسائل قد لا تُحسم إلا بنظريات عميقة جدًا.

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

DLIN مقابل NLIN

عند استبدال "الوقت الخطي على آلة تورينج متعددة الأشرطة" بـ "الوقت متعدد الحدود" في تعريفات P و NP، نحصل على الفئتين DLIN و NLIN . ومن المعروف [ 32 ] أن DLIN ≠ NLIN.

نتائج الحل

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

P = NP

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

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

قد يُحدث حلٌّ يُثبت أن P  =  NP ثورةً في مجال التشفير ، الذي يعتمد على صعوبة بعض المسائل. إن حلاً بنّاءً وفعّالاً [ ملاحظة 4 ] لمسألة NP-كاملة مثل 3-SAT من شأنه أن يُعطّل معظم أنظمة التشفير الحالية، بما في ذلك:

ستحتاج هذه إلى تعديل أو استبدال بحلول آمنة من الناحية النظرية للمعلومات والتي لا تفترض أن P  ≠  NP.

هناك أيضًا فوائد جمة ستترتب على جعل العديد من المسائل الرياضية المستعصية قابلة للحل حاليًا. على سبيل المثال، العديد من مسائل بحوث العمليات مصنفة ضمن فئة NP-complete، مثل أنواع البرمجة العددية ومسألة البائع المتجول . سيكون للحلول الفعالة لهذه المسائل آثار بالغة الأهمية على مجال الخدمات اللوجستية. كما أن العديد من المسائل المهمة الأخرى، مثل بعض مسائل التنبؤ ببنية البروتين ، مصنفة أيضًا ضمن فئة NP-complete؛ [ 36 ] إن جعل هذه المسائل قابلة للحل بكفاءة من شأنه أن يُسهم بشكل كبير في تطوير علوم الحياة والتكنولوجيا الحيوية.

قد تبدو هذه التغييرات ضئيلة مقارنةً بالثورة التي سيُحدثها حلّ مسائل NP-complete بكفاءة في الرياضيات نفسها. وقد أشار غودل، في أفكاره المبكرة حول التعقيد الحسابي، إلى أن وجود طريقة آلية قادرة على حلّ أي مسألة سيُحدث ثورة في الرياضيات: [ 37 ] [ 38 ]

لو وُجدت آلةٌ بالفعل بمعامل φ( n ) ∼ k ⋅ n (أو حتى ∼ k ⋅ n² )، لكان لذلك عواقب بالغة الأهمية. بمعنى آخر، سيعني ذلك بوضوح أنه بالرغم من عدم إمكانية حسم مسألة القرار ، يُمكن استبدال الجهد الذهني الذي يبذله عالم الرياضيات في مسائل الإجابة بنعم أو لا بآلةٍ تمامًا. ففي النهاية، يكفي اختيار عدد طبيعي n كبير جدًا بحيث إذا لم تُقدّم الآلة نتيجة، فلا جدوى من التفكير في المسألة أكثر من ذلك.

وبالمثل، يقول ستيفن كوك (بافتراض ليس فقط وجود برهان، ولكن أيضًا وجود خوارزمية فعالة عمليًا): [ 29 ]

...  سيُحدث هذا ثورة في الرياضيات، إذ سيُمكّن الحاسوب من إيجاد برهان رسمي لأي نظرية ذات برهان معقول الطول، لأن البراهين الرسمية يُمكن التعرف عليها بسهولة في وقت متعدد الحدود. وقد تشمل الأمثلة جميع مسائل جائزة CMI .

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

صرح دونالد كنوث  بأنه قد توصل إلى الاعتقاد بأن P =  NP، لكنه متحفظ بشأن تأثير البرهان المحتمل: [ 39 ]

[...] إذا تخيلنا عددًا M محدودًا ولكنه ضخم للغاية - مثل العدد 10↑↑↑↑3 الذي ناقشته في ورقتي البحثية حول "التعامل مع محدودية الأعداد" - فسيكون هناك عدد هائل من الخوارزميات الممكنة التي تُجري n M عملية حسابية على مستوى البت، أو عمليات جمع أو إزاحة، على n بتًا مُعطى، ومن الصعب حقًا تصديق أن جميع هذه الخوارزميات تفشل. مع ذلك، فإن النقطة الأساسية هي أنني لا أعتقد أن المساواة P  =  NP ستكون مفيدة حتى لو تم إثباتها، لأن مثل هذا الإثبات سيكون على الأرجح غير بنّاء.

يوضح مخطط فئات التعقيد أن P ≠ NP. وقد تم إثبات وجود مسائل ضمن NP ولكن خارج كل من P و NP-complete، في ظل هذا الافتراض، بواسطة نظرية لادنر . [ 20 ]  

P ≠ NP

إن إثبات أن P  ≠  NP سيفتقر إلى الفوائد الحسابية العملية لإثبات أن P  =  NP، ولكنه سيمثل تقدماً كبيراً في نظرية التعقيد الحسابي وسيوجه الأبحاث المستقبلية. وسيُظهر أن العديد من المشكلات الشائعة لا يمكن حلها بكفاءة، مما يسمح للباحثين بالتركيز على الحلول الجزئية أو حلول مشكلات أخرى. ونظراً للاعتقاد السائد بأن P  ≠  NP، فقد تم بالفعل توجيه جزء كبير من هذا البحث. [ 40 ]

لا يزال احتمال أن تكون P  ≠ NP يُبقي مسألة تعقيد الحالة المتوسطة  للمسائل الصعبة في فئة NP مفتوحة . على سبيل المثال، من الممكن أن تتطلب مسألة SAT وقتًا أُسّيًا في أسوأ الحالات، ولكن يمكن حل جميع الحالات المختارة عشوائيًا منها تقريبًا بكفاءة. وصف راسل إمباغليازو خمسة "عوالم" افتراضية قد تنتج عن حلول مختلفة لمسألة تعقيد الحالة المتوسطة. [ 41 ] تتراوح هذه العوالم من "Algorithmica"، حيث P = NP ويمكن حل مسائل مثل SAT بكفاءة في جميع الحالات، إلى "Cryptomania"، حيث P ≠ NP ويسهل توليد حالات صعبة من المسائل خارج P، مع ثلاثة احتمالات وسيطة تعكس توزيعات مختلفة محتملة للصعوبة على حالات المسائل الصعبة من فئة NP. يُطلق على "العالم" الذي تكون فيه P ≠ NP ولكن جميع المسائل في فئة NP قابلة للحل في الحالة المتوسطة اسم "Heuristica" في الورقة البحثية. درست ورشة عمل في جامعة برينستون عام 2009 حالة هذه العوالم الخمسة. [ 42 ]      

نتائج تتعلق بصعوبة الإثبات

على الرغم من أن مسألة P  =  NP لا تزال مفتوحةً رغم جائزة المليون دولار والكم الهائل من الأبحاث المخصصة لها، فقد أسفرت الجهود المبذولة لحلها عن ظهور العديد من التقنيات الجديدة. وعلى وجه الخصوص، أظهرت بعضٌ من أكثر الأبحاث المثمرة المتعلقة بمسألة P  = NP أن تقنيات البرهان الحالية غير كافية للإجابة على السؤال، مما يشير إلى ضرورة اتباع مناهج تقنية جديدة. 

وكدليل إضافي على صعوبة المشكلة، فإن جميع تقنيات الإثبات المعروفة في نظرية التعقيد الحسابي تندرج ضمن أحد التصنيفات التالية، وكلها غير كافية لإثبات أن P  ≠  NP:

تصنيفتعريف
البراهين النسبيةتخيل عالماً يُسمح فيه لكل خوارزمية بالاستعلام من روتين فرعي ثابت يُسمى " أوراكل" (يستطيع الإجابة على مجموعة محددة من الأسئلة في وقت ثابت، مثل أوراكل يحل أي مسألة بائع متجول في خطوة واحدة)، ولا يُحتسب وقت تشغيل الأوراكل ضمن وقت تشغيل الخوارزمية. تنطبق معظم البراهين (وخاصة الكلاسيكية منها) بشكل موحد في عالم الأوراكل بغض النظر عن وظيفة الأوراكل. تُسمى هذه البراهين بالنسبية . في عام 1975، أثبت بيكر وجيل وسولوفاي أن P  =  NP بالنسبة لبعض الأوراكل، بينما P  ≠  NP بالنسبة لأوراكل أخرى. [ 43 ] ولأن البراهين النسبية لا تستطيع إثبات إلا العبارات الصحيحة لجميع الأوراكل الممكنة، فإن هذه التقنيات لا تستطيع حل معضلة P  =  NP.
البراهين الطبيعيةفي عام ١٩٩٣، عرّف ألكسندر رازبوروف وستيفن روديتش فئة عامة من أساليب البرهان لحدود التعقيد الأدنى للدوائر، أطلقوا عليها اسم البراهين الطبيعية . [ ٤٤ ] في ذلك الوقت، كانت جميع حدود الدوائر المعروفة سابقًا طبيعية، واعتُبر تعقيد الدوائر نهجًا واعدًا جدًا لحل معضلة P  =  NP. مع ذلك، بيّن رازبوروف وروديتش أنه في حال وجود دوال أحادية الاتجاه ، فإن P وNP لا يمكن تمييزهما باستخدام أساليب البرهان الطبيعية. على الرغم من أن وجود الدوال أحادية الاتجاه لم يُثبت بعد، إلا أن معظم علماء الرياضيات يعتقدون بوجودها، وسيكون برهان وجودها أقوى بكثير من مجرد القول بأن P  ≠  NP. لذا، من غير المرجح أن تتمكن البراهين الطبيعية وحدها من حل معضلة P  =  NP.
برهان جبريبعد نتيجة بيكر-جيل-سولوفاي، استُخدمت بنجاح تقنيات إثبات جديدة غير نسبية لإثبات أن IP  = PSPACE . مع ذلك، في عام 2008، بيّن سكوت آرونسون وآفي ويغدرسون أن الأداة التقنية الرئيسية المستخدمة في إثبات IP = PSPACE، والمعروفة باسم التحويل الحسابي ، لم تكن كافية لحل P = NP. [ 45 ] يحوّل التحويل الحسابي عمليات الخوارزمية إلى رموز جبرية وحسابية أساسية ، ثم يستخدمها لتحليل طريقة عملها. في إثبات IP = PSPACE ، يحوّلان الصندوق الأسود والدوائر المنطقية إلى مسألة جبرية. [ 45 ] كما ذُكر سابقًا، فقد ثبت أن هذه الطريقة غير مجدية لحل P = NP ومسائل التعقيد الزمني الأخرى .         

تُعد هذه الحواجز سببًا آخر يجعل مشاكل NP-complete مفيدة: إذا أمكن إثبات وجود خوارزمية ذات وقت متعدد الحدود لمشكلة NP-complete، فإن هذا من شأنه أن يحل مشكلة P  =  NP بطريقة لا تستبعدها النتائج المذكورة أعلاه.

تدفع هذه العوائق بعض علماء الحاسوب إلى اقتراح أن مشكلة P مقابل NP قد تكون مستقلة عن أنظمة البديهيات القياسية مثل ZFC (أي لا يمكن إثباتها أو دحضها ضمنها). قد تعني نتيجة الاستقلال إما أن P  ≠  NP وهذا غير قابل للإثبات في (على سبيل المثال) ZFC، أو أن P  =  NP ولكن من غير القابل للإثبات في ZFC صحة أي خوارزميات ذات زمن متعدد الحدود. [ 46 ] مع ذلك، إذا كانت المشكلة غير قابلة للحل حتى مع افتراضات أضعف بكثير تُوسّع بديهيات بيانو للحساب الصحيح، فإن خوارزميات ذات زمن متعدد الحدود تقريبًا موجودة لجميع مشاكل NP. [ 47 ] لذلك، بافتراض (كما يفعل معظم منظري التعقيد) أن بعض مشاكل NP لا تمتلك خوارزميات فعالة، فإن إثبات الاستقلال باستخدام هذه التقنيات مستحيل. وهذا يعني أيضًا أن إثبات الاستقلال عن PA أو ZFC بالتقنيات الحالية ليس أسهل من إثبات أن جميع مشاكل NP تمتلك خوارزميات فعالة.

التوصيفات المنطقية

يمكن إعادة صياغة مشكلة P  =  NP على أنها فئات معينة من العبارات المنطقية، كنتيجة للعمل في التعقيد الوصفي .

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

وبالمثل، فإن NP هي مجموعة اللغات التي يمكن التعبير عنها في منطق الرتبة الثانية الوجودي ، أي منطق الرتبة الثانية المقيد باستبعاد التكميم الشامل على العلاقات والدوال والمجموعات الجزئية. وتتوافق اللغات في التسلسل الهرمي متعدد الحدود ، PH ، مع جميع لغات منطق الرتبة الثانية. وبالتالي، يمكن إعادة صياغة السؤال "هل P مجموعة جزئية فعلية من NP؟" على النحو التالي: "هل يستطيع منطق الرتبة الثانية الوجودي وصف اللغات (ذات البنى الخطية المرتبة المحدودة ذات التوقيع غير التافه) التي لا يستطيع منطق الرتبة الأولى ذو النقطة الثابتة الصغرى وصفها؟". [ 48 ] بل يمكن حذف كلمة "وجودي" من التوصيف السابق، لأن P  =  NP إذا وفقط إذا كانت P  =  PH (إذ أن الأول سيثبت أن NP  =  co-NP، مما يعني بدوره أن NP  =  PH).

خوارزميات الوقت متعدد الحدود

لا توجد خوارزمية معروفة لحل مسائل NP-كاملة تعمل في زمن متعدد الحدود. مع ذلك، توجد خوارزميات معروفة لحل مسائل NP-كاملة، إذا كانت P  =  NP، تعمل الخوارزمية في زمن متعدد الحدود عند قبول الحالات (مع ثوابت ضخمة، مما يجعل الخوارزمية غير عملية). لكن هذه الخوارزميات لا تُصنّف كخوارزميات ذات زمن متعدد الحدود لأن زمن تشغيلها عند رفض الحالات ليس متعدد الحدود. الخوارزمية التالية، منسوبة إلى ليفين (بدون أي توثيق)، هي مثال على ذلك. تقبل هذه الخوارزمية لغة NP-كاملة SUBSET-SUM بشكل صحيح . وتعمل في زمن متعدد الحدود على المدخلات التي تنتمي إلى SUBSET-SUM إذا وفقط إذا كانت P  =  NP.

// خوارزمية تقبل لغة SUBSET-SUM الكاملة من فئة NP. // // هذه خوارزمية ذات زمن متعدد الحدود إذا وفقط إذا كانت P = NP. // // "زمن متعدد الحدود" يعني أنها تُرجع "نعم" في زمن متعدد الحدود عندما // يجب أن تكون الإجابة "نعم"، وتستمر في العمل إلى الأبد عندما تكون الإجابة "لا". // // المدخلات: S = مجموعة منتهية من الأعداد الصحيحة // المخرجات: "نعم" إذا كان مجموع أي مجموعة جزئية من S يساوي 0. // تستمر في العمل إلى الأبد دون أي مخرجات خلاف ذلك. // ملاحظة: "رقم البرنامج M" هو البرنامج الناتج عن // كتابة العدد الصحيح M بالنظام الثنائي، ثم // اعتبار سلسلة البتات هذه برنامجًا. // يمكن توليد كل برنامج ممكن بهذه الطريقة، على الرغم من أن معظمها لا يفعل شيئًا // بسبب أخطاء في بناء الجملة. لكل k = 1...∞ لكل M = 1...K قم بتشغيل البرنامج رقم M لعدد K من الخطوات مع المدخل S إذا كان البرنامج يُخرج قائمة من الأعداد الصحيحة المميزة وجميع الأعداد الصحيحة موجودة في S ومجموع الأعداد الصحيحة يساوي صفرًا ثم أخرج "نعم" وتوقف

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

هذه الخوارزمية غير عملية للغاية، حتى لو كانت P  =  NP. إذا كان أقصر برنامج يمكنه حل مسألة SUBSET-SUM في وقت متعدد الحدود بطول b بت، فإن الخوارزمية المذكورة أعلاه ستجرب ما لا يقل عن 2b - 1 برنامجًا آخر أولاً.

التعريفات الرسمية

P و NP

مسألة القرار هي مسألة تأخذ كمدخل سلسلة نصية w من الأبجدية Σ، وتُخرج "نعم" أو "لا". إذا وُجدت خوارزمية (مثل آلة تورينج ، أو برنامج حاسوبي بذاكرة غير محدودة) تُنتج الإجابة الصحيحة لأي سلسلة نصية طولها n في عدد لا يتجاوز cn k من الخطوات، حيث k و c ثابتان مستقلان عن السلسلة النصية المدخلة، فإننا نقول إن المسألة قابلة للحل في زمن متعدد الحدود ، ونُصنفها ضمن الفئة P. رسميًا، P هي مجموعة اللغات التي يمكن لآلة تورينج حتمية ذات زمن متعدد الحدود أن تُقررها.

P={ل:ل=ل(م) بالنسبة لبعض آلات تورينج الحتمية ذات الوقت متعدد الحدود م}{\displaystyle {\mathsf {P}}=\{L:L=L(M){\text{ لبعض آلات تورينج الحتمية ذات الوقت متعدد الحدود }}M\}}

أين

ل(م)={w∈Σ*:م يقبل w}{\displaystyle L(M)=\{w\in \Sigma ^{*}:M{\text{ accepts }}w\}}

وآلة تورينج الحتمية ذات الوقت متعدد الحدود هي آلة تورينج حتمية M تحقق شرطين:

  1. يتوقف المحرك M عند جميع المدخلات w و
  2. يوجدك∈شمال{\displaystyle k\in N}بحيثتيم(ن)∈يا(نك){\displaystyle T_{M}(n)\in O(n^{k})}، حيث يشير O إلى رمز O الكبير و
تيم(ن)=الأعلى{تم(w):w∈Σ*،|w|=ن}{\displaystyle T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},|w|=n\}}
تم(w)= عدد الخطوات م يتوقف عند الإدخال w.{\displaystyle t_{M}(w)={\text{ عدد الخطوات }}M{\text{ التي تستغرقها للتوقف عند إدخال }}w.}

يمكن تعريف NP بطريقة مماثلة باستخدام آلات تورينج غير الحتمية (الطريقة التقليدية). مع ذلك، يستخدم النهج الحديث مفهوم الشهادة والمُدقِّق . رسميًا، NP هي مجموعة اللغات ذات الأبجدية المحدودة والمُدقِّق الذي يعمل في وقت متعدد الحدود. فيما يلي تعريف "المُدقِّق" :

ليكن L لغة على أبجدية محدودة، Σ.

L ∈ NP إذا وفقط إذا وُجدت علاقة ثنائيةR⊂Σ*×Σ*{\displaystyle R\subset \Sigma ^{*}\times \Sigma ^{*}}وعدد صحيح موجب k بحيث يتحقق الشرطان التاليان:

  1. للجميعx∈Σ*{\displaystyle x\in \Sigma ^{*}}،x∈ل⇔∃y∈Σ*{\displaystyle x\in L\Leftrightarrow \exists y\in \Sigma ^{*}}بحيث يكون ( x , y ) ∈ R و|y|∈يا(|x|ك){\displaystyle |y|\in O(|x|^{k})}؛ و
  2. اللغةلR={x8y:(x،y)∈R}{\displaystyle L_{R}=\{x\#y:(x,y)\in R\}}زيادةΣ∪{8}{\displaystyle \Sigma \cup \{\#\}}يمكن تحديدها بواسطة آلة تورينج حتمية في وقت متعدد الحدود.

تُسمى آلة تورينج التي تقرر L R مدققًا لـ L و y بحيث ( x , y ) ∈ R شهادة عضوية x في L.

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

مثال

يترك

جيامPياSأناتيهـ={x∈شمال|x=صq للأعداد الصحيحة ص،q>1}{\displaystyle \mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ للأعداد الصحيحة }}p,q>1\right\}}
R={(x،y)∈شمال×شمال|1<y≤x و y يقسم x}.{\displaystyle R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ و }}y{\text{ يقسم }}x\right\}.}

إن كون قيمة x مركبة يكافئ كون x عنصرًا من عناصر المجموعة المركبة (COMPOITE). ويمكن إثبات أن المجموعة المركبة (COMPOITE ) تنتمي إلى المجموعة غير المركبة (NP) بالتحقق من أنها تحقق التعريف المذكور أعلاه (إذا عرّفنا الأعداد الطبيعية بتمثيلاتها الثنائية).

كما أن COMPOSITE موجود في P، وهي حقيقة تم إثباتها من خلال اختراع اختبار AKS الأولي . [ 49 ]

اكتمال NP

توجد العديد من الطرق المتكافئة لوصف اكتمال NP.

ليكن L لغة على أبجدية منتهية Σ.

تكون المجموعة L من فئة NP-complete إذا، وفقط إذا، تحققت الشروط التالية:

  1. L ∈ NP؛ و
  2. أي عنصر L ′ في NP قابل للاختزال في وقت متعدد الحدود إلى L (يكتب على النحو التالي)ل′≤صل{\displaystyle L'\leq _{p}L})، أينل′≤صل{\displaystyle L'\leq _{p}L}إذا، وفقط إذا، تحققت الشروط التالية:
    1. يوجد دالة f  : Σ* → Σ* بحيث يكون لدينا لكل w في Σ*:(w∈ل′⇔و(w)∈ل){\displaystyle (w\in L'\Leftrightarrow f(w)\in L)}؛ و
    2. توجد آلة تورينج ذات وقت متعدد الحدود تتوقف عند f ( w ) على شريطها عند أي مدخل w .

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

الحلول المزعومة

على الرغم من أن مسألة P مقابل NP تُعتبر عمومًا مسألة غير محلولة، [ 50 ] فقد ادعى العديد من الباحثين الهواة وبعض الباحثين المحترفين وجود حلول لها. جمع جيرهارد ج. ووجينجر قائمة تضم 116 برهانًا مزعومًا من عام 1986 إلى عام 2016، منها 61 برهانًا على أن P  =  NP، و49 برهانًا على أن P  ≠  NP، و6 برهانات تثبت نتائج أخرى، مثل أن المسألة غير قابلة للحسم. [ 51 ] وقد حظيت بعض المحاولات لحل مسألة P مقابل NP باهتمام إعلامي وجيز، [ 52 ] على الرغم من دحض هذه المحاولات.

يروي فيلم "البائع المتجول" للمخرج تيموثي لانزون قصة أربعة رياضيين استأجرتهم الحكومة الأمريكية لحل مشكلة P مقابل NP. [ 53 ]

في الحلقة السادسة من الموسم السابع من مسلسل عائلة سيمبسون ، بعنوان " بيت الرعب السادس "، تظهر المعادلة P  = NP بعد وقت قصير من دخول هومر عن طريق الخطأ إلى "البعد الثالث". [ 54 ] [ 55 ] 

في الحلقة الثانية من الموسم الثاني من مسلسل Elementary ، بعنوان "Solve for X" ، يحقق هولمز وواتسون في جرائم قتل علماء رياضيات كانوا يحاولون حل مسألة P مقابل NP. [ 56 ] [ 57 ]

في حلقة " ضع رأسك على كتفي " من الموسم الثاني لمسلسل الرسوم المتحركة "فيوتوراما" ، يظهر تلميح بصري لمشكلة P مقابل NP في الخلفية. في مشهد يلجأ فيه فراي وزميلته إيمي وونغ إلى خزانة المؤن لإجراء محادثة خاصة، يجلس خلفهما على رف بجوار صندوق مكتوب عليه "فاصوليا الطوارئ" كتابان متطابقان في الحجم، أحدهما يحمل علامة "P" والآخر "NP". [ 58 ] [ 59 ]

مشاكل مماثلة

انظر أيضاً

ملحوظات

  1. ↑ يمكن لآلة تورينغ غير الحتمية الانتقال إلى حالة لا تحددها الحالة السابقة. يمكن لهذه الآلة حل مسألة NP في وقت متعدد الحدود بالوصول إلى حالة الإجابة الصحيحة (بمحض الصدفة)، ثم التحقق منها بالطريقة التقليدية. لا تُعد هذه الآلات عملية لحل المشكلات الواقعية، ولكن يمكن استخدامها كنماذج نظرية.
  2. ↑ أعرب ناش عن شكوكه في إمكانية إثبات هذه الفرضية: "طبيعة هذه الفرضية هي أنني لا أستطيع إثباتها، حتى بالنسبة لنوع بسيط من التشفير. ولا أتوقع أن يتم إثباتها".
  3. ↑ أُجريت الاستطلاعات في الأعوام 2001 و2011 و2018، ولكن نُشرت نتائجها في الأعوام 2002 و2012 و2019 على التوالي. [ 11 ]
  4. ↑ يعتمد مدى كفاءة الحل اللازم لتشكيل تهديد للتشفير على التفاصيل. حل منيا(شمال2){\displaystyle O(N^{2})}إن استخدام حد ثابت معقول سيكون كارثيًا. من ناحية أخرى، فإن الحل الذي هوΩ(شمال4){\displaystyle \Omega (N^{4})}في معظم الحالات، لن يشكل ذلك خطراً عملياً مباشراً.

مراجع

  1. ↑ "شرح: الفرق بين P و NP" . أخبار معهد ماساتشوستس للتكنولوجيا | معهد ماساتشوستس للتكنولوجيا . 29 أكتوبر 2009. تم الاطلاع عليه في 6 مارس 2026 .
  2. ↑ فورتناو، لانس (2009). "وضع مشكلة P مقابل NP" (ملف PDF) . مجلة اتصالات ACM . 52 (9): 78-86 . CiteSeerX 10.1.1.156.767 . doi : 10.1145/1562164.1562186 . S2CID 5969255. مؤرشف من الأصل (ملف PDF) في 24 فبراير 2011. تم الاطلاع عليه في 26 يناير 2010 .  
  3. ↑ فورتناو، لانس (2013). التذكرة الذهبية: P، NP، والبحث عن المستحيل . برينستون، نيوجيرسي: مطبعة جامعة برينستون. ISBN 9780691156491.
  4. ↑ كوك، ستيفن (1971). "تعقيد إجراءات إثبات النظريات" . وقائع الندوة السنوية الثالثة لجمعية آلات الحوسبة حول نظرية الحوسبة . الصفحات 151-158 . doi : 10.1145/800157.805047 . ISBN  9781450374644. S2CID 7573663 . 
  5. ↑ ليفين، إل إيه (1973).الفوائد العالمية مجزية[ مشاكل نقل المعلومات ] . مشكلة. معلومات مسبقة (بالروسية). 9 (3): 115- 116.
  6. ↑ وكالة الأمن القومي (2012). "رسائل من جون ناش" (ملف PDF) . انظر الصفحات 7-8. مؤرشف (ملف PDF) من الأصل في 9 نوفمبر 2018.{{cite web}}: CS1 maint: location ( link )
  7. ↑ هارتمانيس، يوريس. "غودل، فون نيومان، ومسألة P = NP" (ملف PDF) . نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية . 38 : 101-107 .
  8. ↑ سيبسر، مايكل: مقدمة في نظرية الحوسبة، الطبعة الثانية، الطبعة الدولية ، صفحة 270. تومسون كورس تكنولوجي، 2006. التعريف 7.19 والنظرية 7.20.
  9. 1 2 3 4 غاسارش، ويليام آي. ( يونيو 2002). "استطلاع الرأي P=?NP" (ملف PDF) . أخبار SIGACT . 33 (2): 34-47 . CiteSeerX 10.1.1.172.1005 . doi : 10.1145/564585.564599 . S2CID 36828694. مؤرشف (ملف PDF) من الأصل في 15 يونيو 2007.  
  10. ↑ غاسارش، ويليام آي. " الاستطلاع الثاني P=?NP" (ملف PDF) . أخبار SIGACT . 74. مؤرشف (ملف PDF) من الأصل في 24 يناير 2014.
  11. 1 2 3 4 "مقال رأي: الخيار الثالث =؟ استطلاع الرأي الوطني 1" (ملف PDF) . مؤرشف (ملف PDF) من النسخة الأصلية بتاريخ 31 مارس 2019. تم الاطلاع عليه بتاريخ 25 مايو 2020 .
  12. ↑ آرونسون، سكوت. "محاضرة PHYS771 رقم 6: P، NP، وأصدقائهم" . تم الاطلاع عليه بتاريخ 27 أغسطس 2007 .
  13. ↑ "دورة ماجستير العلوم: أسس علوم الحاسوب" . www.cs.ox.ac.uk. تاريخ الاطلاع: 25 مايو 2020 .
  14. ↑ كولبورن، تشارلز ج. (1984). "تعقيد إكمال المربعات اللاتينية الجزئية" . الرياضيات التطبيقية المنفصلة . 8 (1): 25-30 . doi : 10.1016/0166-218X(84)90075-1 .
  15. ↑ هولير، آي. (1981). "اكتمال NP لبعض مسائل تقسيم الحواف". مجلة SIAM للحوسبة 10 ( 4): 713-717 . doi : 10.1137/0210054 .
  16. ↑ فرانكل، أفيزري ؛ ليختنشتاين، د. (1981). "حساب استراتيجية مثالية للشطرنج من الرتبة n × n يتطلب وقتًا أُسّيًا بالنسبة إلى n ". مجلة نظرية التوافيق . السلسلة أ. 31 (2): 199-214 . doi : 10.1016/0097-3165(81)90016-9 .
  17. ↑ إيبستين، ديفيد . "التعقيد الحسابي للألعاب والألغاز" .
  18. ↑ فيشر، مايكل ج .؛ رابين، مايكل أ. (1974). "التعقيد الأسي الفائق لحساب بريسبرغر" . وقائع ندوة SIAM-AMS في الرياضيات التطبيقية . 7 : 27-41 . مؤرشف من الأصل في 15 سبتمبر 2006. تم الاطلاع عليه في 15 أكتوبر 2017 .
  19. ↑ فاليانت، ليزلي ج. (1979). "تعقيد مسائل التعداد والموثوقية". مجلة SIAM للحوسبة . 8 (3): 410-421 . doi : 10.1137/0208032 .
  20. 1 2 لادنر، ر. إي. (1975). "حول بنية قابلية الاختزال في زمن متعدد الحدود" . مجلة ACM . 22 : 151-171. انظر النتيجة 1.1. doi : 10.1145/321864.321877 . S2CID 14352974 . 
  21. ↑ أرفيند، فيكرامان؛ كورور، بيوش ب. (2006). "تماثل الرسوم البيانية موجود في SPP". المعلومات والحوسبة . 204 (5): 835-852 . doi : 10.1016/j.ic.2006.02.002 .
  22. ↑ شونينغ، أوفه (1988). "تماثل الرسوم البيانية في التسلسل الهرمي الأدنى". مجلة علوم الحاسوب والنظم . 37 (3): 312-323 . doi : 10.1016/0022-0000(88)90010-4 .
  23. ↑ باباي، لازلو (2018). "المجموعة، الرسوم البيانية، الخوارزميات: مشكلة تماثل الرسوم البيانية". وقائع المؤتمر الدولي للرياضيات - ريو دي جانيرو 2018. المجلد الرابع. محاضرات مدعوة . دار النشر العالمية للعلوم، هاكنساك، نيوجيرسي. الصفحات 3319-3336 . MR 3966534 .  
  24. ↑ لانس فورتناو . مدونة التعقيد الحسابي: درس التعقيد لهذا الأسبوع: التحليل إلى عوامل . 13 سبتمبر 2002.
  25. ↑ بيسينجر، د. 2003. "أين تكمن مشاكل حقيبة الظهر الصعبة؟" تقرير فني 2003/08، قسم علوم الحاسوب، جامعة كوبنهاغن، كوبنهاغن، الدنمارك
  26. ↑ كاواراباياشي، كين-إيتشي؛ كوباياشي، يوسوكي؛ ريد، بروس (2012). "مسألة المسارات المنفصلة في زمن تربيعي" . مجلة نظرية التوافيق . السلسلة ب. 102 (2): 424-435 . doi : 10.1016/j.jctb.2011.07.004 .
  27. ↑ جونسون، ديفيد س. (1987). "عمود اكتمال NP: دليل مستمر (الطبعة 19)". مجلة الخوارزميات . 8 (2): 285-303 . CiteSeerX 10.1.1.114.3864 . doi : 10.1016/0196-6774(87)90043-5 . 
  28. ↑ غوندزيو، جاك؛ تيرلاكي، تاماس (1996). "3 نظرة حسابية لطرق النقطة الداخلية" . في جيه إي بيزلي (محرر). التطورات في البرمجة الخطية والبرمجة العددية الصحيحة . سلسلة محاضرات أكسفورد في الرياضيات وتطبيقاتها. المجلد 4. نيويورك: مطبعة جامعة أكسفورد. الصفحات 103-144 . MR 1438311. ملف Postscript متاح على موقع غوندزيو الإلكتروني وعلى موقع جامعة ماكماستر الإلكتروني الخاص بتيرلاكي .   
  29. 1 2 كوك، ستيفن (أبريل 2000). "مشكلة P مقابل NP" (ملف PDF) . معهد كلاي للرياضيات . مؤرشف (ملف PDF) من الأصل في 16 ديسمبر 2013. تم الاطلاع عليه في 18 أكتوبر 2006 .
  30. ↑ روزنبرغر، جاك (مايو 2012). "نتائج استطلاع الرأي بين مؤيدي ومعارضي الحزب" . اتصالات رابطة آلات الحوسبة . 55 (5): 10.
  31. ↑ آرونسون، سكوت (4 سبتمبر 2006). "أسباب للإيمان" .، النقطة 9.
  32. ^ بالكزار، خوسيه لويس. دياز، جوزيب؛ جابارو، يواكيم (1990). التعقيد الهيكلي الثاني . سبرينغر فيرلاغ. رقم ISBN 3-540-52079-1.، النظرية 3.9
  33. ↑ انظر: هوري، س.؛ واتانابي، أ. (1997). "توليد الحالات الصعبة لمسألة SAT". الخوارزميات والحوسبة . سلسلة محاضرات في علوم الحاسوب. المجلد 1350. سبرينغر. الصفحات 22-31 . arXiv : cs/9809117 . Bibcode : 1998cs........9117H . doi : 10.1007/3-540-63890-3_4 . ISBN   978-3-540-63890-2.لتقليل عملية التحليل إلى SAT. تُترجم مشكلة تحليل 512 بت (8400 مليون سنة حسابية عند تحليلها) إلى مشكلة SAT تتكون من 63652 متغيرًا و406860 بندًا.
  34. ↑ انظر، على سبيل المثال، ماساتشي، ف.؛ مارارو، ل. (2000). "التحليل المنطقي للتشفير كمسألة SAT". مجلة الاستدلال الآلي . 24 (1): 165-203 . CiteSeerX 10.1.1.104.962 . doi : 10.1023/A:1006326723002 . S2CID 3114247 .  حيث يتم ترميز مثال لخوارزمية DES كمسألة SAT تحتوي على 10336 متغيرًا و61935 بندًا. أما مثال مسألة 3DES فسيكون حجمه أكبر بثلاث مرات تقريبًا.
  35. ↑ دي، ديبابراتيم؛ كوماراسوبرامانيان، أبيشيك؛ فينكاتيسان، راماراثنام (2007). "هجمات الانعكاس على دوال التجزئة الآمنة باستخدام حلول SAT". نظرية وتطبيقات اختبار الإرضاء - SAT 2007. المؤتمر الدولي حول نظرية وتطبيقات اختبار الإرضاء. سبرينغر. ص 377-382 . doi : 10.1007/978-3-540-72788-0_36 .  
  36. ↑ بيرغر، ب .؛ لايتون، ت. (1998). "طي البروتين في نموذج الكاره للماء-المحب للماء (HP) هو مسألة كاملة من فئة NP". مجلة علم الأحياء الحاسوبي . 5 (1): 27-40 . CiteSeerX 10.1.1.139.5547 . doi : 10.1089/cmb.1998.5.27 . PMID 9541869 .  
  37. ↑ تاريخ هذه الرسالة وترجمتها من سيبر، مايكل. "تاريخ ومكانة مسألة P مقابل NP" (ملف PDF) . مؤرشف (ملف PDF) من الأصل في 2 فبراير 2014.
  38. ↑ جونسون، ديفيد س. (أغسطس 2012). "تاريخ موجز لمسألة الاكتمال غير القطعي، 1954-2012". في: غروتشل، م. (محرر). قصص التحسين (ملف PDF) . دوكيومنتا ماثيماتيكا. ص 359-376 . ISBN  978-3-936609-58-5ISSN 1431-0643​​ 
  39. ↑ كنوت، دونالد إي. (20 مايو 2014). عشرون سؤالاً لدونالد كنوت . إنفورم آي تي . تم الاطلاع عليه في 20 يوليو 2014 .
  40. ↑ فولدز، إل آر (أكتوبر 1983). "نهج حل المشكلات الاستدلالي". مجلة جمعية بحوث العمليات . 34 (10): 927-934 . doi : 10.2307/2580891 . JSTOR 2580891 . 
  41. ↑ R. Impagliazzo, "A personal view of average-case complex" , p. 134, 10th Annual Structure in ComplexTheory Conference (SCT'95), 1995.
  42. ↑ "البرنامج المبدئي لورشة العمل حول "التعقيد والتشفير: وضع عوالم إمباغليازو"تمت أرشفة هذا النص من المصدر الأصلي في 15 نوفمبر 2013.
  43. ↑ بيكر، تي بي؛ جيل، جيه؛ سولوفاي، آر. (1975). "نسبية سؤال P = ؟ NP". مجلة SIAM للحوسبة . 4 (4): 431-442 . doi : 10.1137/0204037 .
  44. ↑ رازبوروف، ألكسندر أ.؛ ستيفن روديتش (1997). "البراهين الطبيعية" . مجلة علوم الحاسوب والنظم . 55 (1): 24-35 . doi : 10.1006/jcss.1997.1494 .
  45. 1 2 آرونسون، س.؛ ويغدرسون، أ. (2008). الجبر: عائق جديد في نظرية التعقيد (ملف PDF) . وقائع مؤتمر ACM STOC'2008. الصفحات 731-740 . doi : 10.1145/1374376.1374481 . مؤرشف (ملف PDF) من الأصل في 21 فبراير 2008. 
  46. ↑ آرونسون، سكوت . "هل P مقابل NP مستقلان رسميًا؟" (ملف PDF) . مؤرشف (PDF) من الأصل في 16 يناير 2017..
  47. ↑ بن ديفيد، شاي؛ هاليفي، شاي (1992). حول استقلالية P مقابل NP . التخنيون (تقرير فني). المجلد 714. مؤرشف من الأصل (GZIP) في 2 مارس 2012. .
  48. ↑ إلفيرا مايوردومو. “P vs NP” أرشفة 16 فبراير 2012 في آلة Wayback. Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).
  49. ^ أغراوال، مانيندرا؛ كيال، نيراج؛ ساكسينا، نيتين (2004). "PRIMEs موجودة في P" (PDF) . حوليات الرياضيات . 160 (2): 781-793 . دوى : 10.4007 / Annals.2004.160.781 . جستور 3597229 . أرشفة (PDF) من النسخة الأصلية في 26 سبتمبر 2006. 
  50. ↑ ماركوف، جون (8 أكتوبر 2009). "بغض النظر عن الجوائز، فإن لغز P-NP له عواقب" . صحيفة نيويورك تايمز .
  51. ↑ جيرهارد ج. ووجينجر . "صفحة P مقابل NP" . تم الاطلاع عليه بتاريخ 24 يونيو 2018 .
  52. ↑ ماركوف، جون (16 أغسطس 2010). "الخطوة 1: نشر دليل مراوغ. الخطوة 2: مشاهدة الألعاب النارية" . صحيفة نيويورك تايمز . تم الاطلاع عليه في 20 سبتمبر 2010 .
  53. ^ جيري ، دنكان (26 أبريل 2012). "يتناول فيلم "البائع المتجول" تداعيات تساوي P مع NP . (موقع Wired UK ، تاريخ الاطلاع: 26 أبريل 2012 ).
  54. ↑ هارديستي، لاري (29 أكتوبر 2009). "شرح: P مقابل NP" .
  55. ↑ شادية، عجم (13 سبتمبر 2013). "ما هي مشكلة P مقابل NP؟ ولماذا هي مهمة؟" .
  56. ↑ غاسارش، ويليام (7 أكتوبر 2013). "هل P مقابل NP أمرٌ بديهي؟ لا، P مقابل NP ليس بديهيًا على الإطلاق" . blog.computationalcomplexity.org . تاريخ الاسترجاع: 6 يوليو 2018 .
  57. ↑ كيركباتريك، نويل (4 أكتوبر 2013). "مراجعة مسلسل Elementary Solve for X: Sines of Murder" . TV.com . مؤرشف من الأصل في 7 يوليو 2018. تم الاطلاع عليه في 6 يوليو 2018 .
  58. ↑ كريس لاودون (مخرج)، كين كيلر (كاتب) (13 فبراير 2000). "ضع رأسك على كتفي". فيوتوراما . الموسم الثاني. الحلقة السابعة. فوكس.
  59. ^ جورجولياس، توم؛ غرينوالد ، سارة ج. ويشتريتش، مارك (2004). "فوتثرما πk الرياضيات في عام 3000" . آفاق الرياضيات . 11 (4): 12- 15.
  60. 1 2 ويغدرسون، آفي (2019). الرياضيات والحوسبة: نظرية تُحدث ثورة في التكنولوجيا والعلوم . مطبعة جامعة برينستون. ISBN 978-0-691-18913-0.
  61. ↑ إل جي فاليانت. فئات الاكتمال في الجبر. في وقائع المؤتمر الحادي عشر لجمعية الحوسبة الآلية STOC، الصفحات 249-261، 1979.

مصادر

  • رايتشل كرويل (28 مايو 2021). "أهم المسائل غير المحلولة في الرياضيات لا تزال غامضة في معظمها . لم يُحل سوى مسألة واحدة من مسائل جائزة الألفية السبع التي سُميت قبل 21 عامًا" . www.scientificamerican.com . تاريخ الاطلاع: 21 يونيو 2021. تتعلق هذه المسألة بمسألة ما إذا كانت المسائل التي يسهل التحقق منها (فئة من الاستفسارات تُسمى NP) لها أيضًا حلول يسهل إيجادها (فئة تُسمى P).
  • هوش، ويليام ل. (11 أغسطس 2009). "مسائل الرياضيات من النوع P مقابل النوع NP" . موسوعة بريتانيكا . تم الاطلاع عليه في 20 يونيو 2021 .
  • " مسألة P مقابل NP" . www.claymath.org (كوك، ليفين) . مؤرشف من الأصل في 18 يونيو 2021. تم الاطلاع عليه في 20 يونيو 2021. لنفترض أنك تُنظم سكنًا لمجموعة من 400 طالب جامعي. المساحة محدودة، ولن يحصل سوى 100 طالب على أماكن في السكن الجامعي. ومما يزيد الأمر تعقيدًا، أن عميد الكلية قدّم لك قائمة بأزواج من الطلاب غير المتوافقين، وطلب ألا يظهر أي زوج من هذه القائمة في اختيارك النهائي. هذا مثال لما يُطلق عليه علماء الحاسوب "مسألة NP"...

للمزيد من القراءة