اكتمال NP

في نظرية التعقيد الحسابي ، تكون المشكلة NP-كاملة عندما:

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

الاسم "NP-complete" هو اختصار لـ "nondeterministic polynomial-time complete". في هذا الاسم، يشير "nondeterministic" إلى آلات تورنج غير حتمية ، وهي طريقة لصياغة فكرة خوارزمية البحث بالقوة الغاشمة رياضيًا. يشير الوقت متعدد الحدود إلى مقدار الوقت الذي يُعتبر "سريعًا" لخوارزمية حتمية للتحقق من حل واحد، أو لآلة تورنج غير حتمية لإجراء البحث بالكامل. يشير " Complete " إلى خاصية القدرة على محاكاة كل شيء في نفس فئة التعقيد .

بتعبير أدق، يجب أن يرتبط كل مدخل للمشكلة بمجموعة من الحلول ذات طول متعدد الحدود، ويمكن اختبار صحة كل منها بسرعة (في زمن متعدد الحدود )، ^[2] بحيث يكون الناتج لأي مدخل "نعم" إذا كانت مجموعة الحلول غير فارغة و"لا" إذا كانت فارغة. تسمى فئة التعقيد للمشكلات من هذا النموذج NP ، وهو اختصار لـ "زمن متعدد الحدود غير حتمي". يقال إن المشكلة NP-hard إذا كان من الممكن تحويل كل شيء في NP في زمن متعدد الحدود إليه حتى لو لم يكن في NP. تكون المشكلة NP-complete إذا كانت في NP وNP-hard. تمثل مشاكل NP-complete أصعب المشاكل في NP. إذا كانت بعض مشاكل NP-complete لها خوارزمية زمن متعدد الحدود، فإن جميع المشاكل في NP كذلك. غالبًا ما يشار إلى مجموعة مشاكل NP-complete بواسطة NP-C أو NPC .

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

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

ملخص

توجد مشكلات NP-complete في NP ، وهي مجموعة مشكلات القرار التي يمكن التحقق من حلولها في زمن متعدد الحدود؛ ويمكن تعريف NP على نحو مكافئ على أنها مجموعة مشكلات القرار التي يمكن حلها في زمن متعدد الحدود على آلة تورنج غير حتمية . تكون المشكلة p في NP مكتملة NP إذا كان من الممكن تحويل (أو اختزال) كل مشكلة أخرى في NP إلى p في زمن متعدد الحدود. ^{[ بحاجة لمصدر ]}

ليس من المعروف ما إذا كان من الممكن حل كل مشكلة في NP بسرعة - وهذا ما يسمى مشكلة P مقابل NP . ولكن إذا كان من الممكن حل أي مشكلة NP-complete بسرعة، فيمكن حل كل مشكلة في NP ، لأن تعريف مشكلة NP-complete ينص على أن كل مشكلة في NP يجب أن تكون قابلة للاختزال بسرعة إلى كل مشكلة NP-complete (أي أنه يمكن اختزالها في وقت متعدد الحدود). وبسبب هذا، غالبًا ما يقال إن مشاكل NP-complete أصعب أو أكثر صعوبة من مشاكل NP بشكل عام. ^{[ بحاجة لمصدر ]}

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

تعتبر مشكلة القرار كاملة NP إذا: ^[^{بحاجة لمصدر}^] $\scriptstyle C$

$\scriptstyle C$ يوجد في NP، و
يمكن تقليص كل مشكلة في NP إلى زمن متعدد الحدود. ^[3] $\scriptstyle C$

$\scriptstyle C$ يمكن إثبات أن الحل المرشح في NP يمكن التحقق منه في زمن متعدد الحدود. $\scriptstyle C$

لاحظ أن المشكلة التي تلبي الشرط 2 يقال عنها أنها NP-hard ، سواء كانت تلبي الشرط 1 أم لا. ^[4]

إحدى نتائج هذا التعريف هي أنه إذا كان لدينا خوارزمية زمنية متعددة الحدود (على UTM ، أو أي آلة مجردة مكافئة لتورنج ) لـ ، فيمكننا حل جميع المشكلات في NP في زمن متعدد الحدود. $\scriptstyle C$

خلفية

تم تقديم مفهوم اكتمال NP في عام 1971 (انظر نظرية كوك-ليفين )، على الرغم من أن مصطلح اكتمال NP تم تقديمه لاحقًا. في مؤتمر STOC لعام 1971 ، كان هناك نقاش عنيف بين علماء الكمبيوتر حول ما إذا كان من الممكن حل مشكلات NP-complete في وقت متعدد الحدود على آلة تورنج حتمية . نجح جون هوبكروفت في إقناع الجميع في المؤتمر بأن مسألة ما إذا كانت مشكلات NP-complete قابلة للحل في وقت متعدد الحدود يجب تأجيلها إلى تاريخ لاحق، حيث لم يكن لدى أحد أي أدلة رسمية لادعاءاتهم بطريقة أو بأخرى. ^[^{بحاجة لمصدر}^] يُعرف هذا باسم "مسألة ما إذا كان P = NP".

لم يتمكن أحد حتى الآن من تحديد ما إذا كانت مسائل NP-complete قابلة للحل فعليًا في زمن متعدد الحدود، مما يجعل هذه واحدة من أعظم المسائل التي لم تُحل في الرياضيات . يقدم معهد كلاي للرياضيات مكافأة قدرها مليون دولار أمريكي ( جائزة الألفية ) لأي شخص لديه دليل رسمي على أن P = NP أو أن P ≠NP. ^[5]

إن وجود مسائل NP-complete ليس واضحًا. تنص نظرية كوك-ليفين على أن مسألة قابلية الإشباع البولياني هي مسألة NP-complete، وبالتالي فهي تؤكد وجود مثل هذه المسائل. في عام 1972، أثبت ريتشارد كارب أن العديد من المسائل الأخرى كانت أيضًا NP-complete (انظر مسائل كارب الـ 21 NP-complete )؛ وبالتالي، هناك فئة من مسائل NP-complete (بالإضافة إلى مسألة قابلية الإشباع البولياني). منذ النتائج الأصلية، تم إثبات أن آلاف المسائل الأخرى هي NP-complete من خلال التخفيضات من مسائل أخرى ثبت سابقًا أنها NP-complete؛ تم جمع العديد من هذه المسائل في Garey & Johnson (1979).

مسائل NP-كاملة

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

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

غالبًا ما يكون هناك فرق صغير فقط بين مشكلة في P ومشكلة مكتملة NP. على سبيل المثال، تظل مشكلة قابلية الإرضاء 3 ، وهي قيد لمشكلة قابلية الإرضاء المنطقية، مكتملة NP، في حين أن مشكلة قابلية الإرضاء 2 الأكثر تقييدًا قليلاً موجودة في P (على وجه التحديد، إنها مكتملة NL )، ولكن مشكلة max. 2-sat. الأكثر عمومية قليلاً هي مرة أخرى مكتملة NP. تحديد ما إذا كان يمكن تلوين الرسم البياني بلونين موجود في P، ولكن مع 3 ألوان يكون مكتملًا NP، حتى عند تقييده بالرسوم البيانية المستوية . تحديد ما إذا كان الرسم البياني عبارة عن دورة أو ثنائي الأجزاء سهل للغاية (في L )، ولكن العثور على أقصى ثنائي الأجزاء أو رسم بياني فرعي لدورة قصوى يكون مكتملًا NP. يمكن حساب حل مشكلة حقيبة الظهر ضمن أي نسبة مئوية ثابتة من الحل الأمثل في وقت متعدد الحدود، ولكن العثور على الحل الأمثل يكون مكتملًا NP.

مشاكل متوسطة

من الأمثلة المثيرة للاهتمام مشكلة تماثل الرسم البياني ، وهي مشكلة نظرية الرسم البياني لتحديد ما إذا كان تماثل الرسم البياني موجودًا بين رسمين بيانيين. يكون الرسمان البيانيان متماثلين إذا كان من الممكن تحويل أحدهما إلى الآخر ببساطة عن طريق إعادة تسمية الرؤوس . ضع في اعتبارك المشكلتين التاليتين:

تماثل الرسم البياني: هل الرسم البياني G1 _متماثل مع الرسم البياني _G2 ؟
تماثل الرسم البياني الفرعي: هل الرسم البياني G1 _متماثل مع الرسم البياني الفرعي للرسم البياني _G2 ؟

تعتبر مشكلة تماثل الرسم البياني الجزئي كاملة من نوع NP. يُشتبه في أن مشكلة تماثل الرسم البياني ليست كاملة من نوع P ولا من نوع NP، على الرغم من أنها من نوع NP. هذا مثال لمشكلة يُعتقد أنها صعبة ، ولكن لا يُعتقد أنها كاملة من نوع NP. تسمى هذه الفئة مشاكل NP-Intermediate وتوجد فقط إذا كانت P≠NP.

حل مسائل NP-complete

في الوقت الحاضر، تتطلب جميع الخوارزميات المعروفة لمشكلات NP-complete وقتًا يتجاوز حدودًا كبيرة في حجم الإدخال. تحتوي مشكلة غطاء الرأس على ^[6] لبعضها ومن غير المعروف ما إذا كانت هناك أي خوارزميات أسرع. $O(1.2738^{k}+nk)$ $k>0$

يمكن تطبيق التقنيات التالية لحل المشكلات الحسابية بشكل عام، وغالبًا ما تؤدي إلى ظهور خوارزميات أسرع بشكل كبير:

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

أحد الأمثلة على الخوارزمية الاستدلالية هو خوارزمية التلوين الجشع دون المستوى الأمثل المستخدمة لتلوين الرسم البياني أثناء مرحلة تخصيص السجل لبعض المترجمين، وهي تقنية تسمى تخصيص السجل العالمي بتلوين الرسم البياني . كل رأس هو متغير، يتم رسم الحواف بين المتغيرات التي يتم استخدامها في نفس الوقت، وتشير الألوان إلى السجل المخصص لكل متغير. نظرًا لأن معظم أجهزة RISC بها عدد كبير إلى حد ما من السجلات العامة، فإن النهج الاستدلالي فعال لهذا التطبيق. $O(n\log n)$

الاكتمال تحت أنواع مختلفة من الاختزال

في تعريف NP-complete المذكور أعلاه، تم استخدام مصطلح الاختزال بالمعنى الفني للاختزال في زمن كثير الحدود .

هناك نوع آخر من الاختزال وهو اختزال تورينج في زمن متعدد الحدود . تكون المشكلة قابلة للاختزال في زمن متعدد الحدود إلى مشكلة إذا كان بإمكان المرء كتابة برنامج يستدعي هذا البرنامج الفرعي ويحل في زمن متعدد الحدود، وذلك في ضوء برنامج فرعي يتم حله في زمن متعدد الحدود. وهذا يتناقض مع قابلية الاختزال من واحد إلى واحد، والتي لها قيد مفاده أن البرنامج لا يمكنه استدعاء البرنامج الفرعي إلا مرة واحدة، ويجب أن تكون قيمة الإرجاع للبرنامج الفرعي هي قيمة الإرجاع للبرنامج. $\scriptstyle X$ $\scriptstyle Y$ $\scriptstyle Y$ $\scriptstyle X$

إذا تم تعريف النظير لـ NP-complete باستخدام اختزالات تورينج بدلاً من الاختزالات المتعددة إلى واحد، فإن مجموعة المشاكل الناتجة لن تكون أصغر من NP-complete؛ إنه سؤال مفتوح عما إذا كانت ستكون أكبر من ذلك.

نوع آخر من الاختزال يستخدم أيضًا غالبًا لتحديد اكتمال NP هو الاختزال متعدد-واحد في الفضاء اللوغاريتمي وهو اختزال متعدد-واحد يمكن حسابه بكمية لوغاريتمية فقط من الفضاء. نظرًا لأن كل عملية حسابية يمكن إجراؤها في الفضاء اللوغاريتمي يمكن إجراؤها أيضًا في زمن متعدد الحدود، فمن الطبيعي أن يكون هناك اختزال متعدد-واحد في الفضاء اللوغاريتمي، وبالتالي إذا كان هناك اختزال متعدد-واحد في الفضاء اللوغاريتمي، فسيكون هناك أيضًا اختزال متعدد-واحد في زمن متعدد الحدود. هذا النوع من الاختزال أكثر دقة من الاختزالات الأكثر شيوعًا متعدد-واحد في زمن متعدد الحدود، ويسمح لنا بالتمييز بين فئات أكثر مثل P-complete . ما إذا كان تعريف التغييرات في NP-complete تحت هذه الأنواع من الاختزالات لا يزال مشكلة مفتوحة. جميع مشاكل NP-complete المعروفة حاليًا هي NP-complete تحت اختزالات الفضاء اللوغاريتمي. تظل جميع مشاكل NP-complete المعروفة حاليًا NP-complete حتى تحت اختزالات أضعف بكثير مثل الاختزالات والتخفيضات . من المعروف أن بعض مشاكل NP-Complete مثل SAT مكتملة حتى تحت إسقاطات زمنية متعددة اللوغاريتمات. ^[7] ومع ذلك، فمن المعروف أن التخفيضات AC ⁰ تحدد فئة أصغر تمامًا من التخفيضات في زمن متعدد الحدود. ^[8] $AC_{0}$ $NC_{0}$

تسمية

وفقًا لدونالد كنوث ، تم ترويج اسم "NP-complete" من قبل ألفريد آهو وجون هوبكروفت وجيفري أولمان في كتابهم المدرسي الشهير "تصميم وتحليل خوارزميات الكمبيوتر". ويذكر أنهم قدموا التغيير في أدلة الطباعة للكتاب (من "Polynomially-complete")، وفقًا لنتائج استطلاع أجراه لمجتمع علوم الكمبيوتر النظرية . ^[9] تضمنت الاقتراحات الأخرى المقدمة في الاستطلاع ^[10] " Herculean "، و"formidable"، و "hard-boiled" لـ Steiglitz تكريمًا لـ Cook، واختصار Shen Lin "PET"، والذي يرمز إلى "الوقت الأسي المحتمل"، ولكن اعتمادًا على الطريقة التي سلكتها مشكلة P مقابل NP ، يمكن أن يرمز إلى "الوقت الأسي القابل للإثبات" أو "الوقت الأسي السابق". ^[11]

المفاهيم الخاطئة الشائعة

المفاهيم الخاطئة التالية شائعة. ^[12]

"تعتبر مسائل NP-complete أصعب مسائل معروفة." ونظرًا لأن مسائل NP-complete تكون في NP، فإن وقت تشغيلها يكون أسيًا على الأكثر. ومع ذلك، فقد ثبت أن بعض المسائل تتطلب وقتًا أطول، على سبيل المثال حساب بريسبرجر . وقد ثبت أيضًا أنه لا يمكن حل بعض المسائل على الإطلاق، على سبيل المثال مشكلة التوقف .
"إن المشكلات الكاملة من النوع NP صعبة لأن هناك العديد من الحلول المختلفة." من ناحية، هناك العديد من المشكلات التي لها مساحة حل كبيرة بنفس القدر، ولكن يمكن حلها في زمن متعدد الحدود (على سبيل المثال شجرة الامتداد الدنيا ). من ناحية أخرى، هناك مشكلات من النوع NP مع حل واحد على الأكثر وهي صعبة الحل من النوع NP في ظل الاختزال العشوائي في زمن متعدد الحدود (انظر نظرية فاليانت-فازيراني ).
"يتطلب حل المشكلات الكاملة ذات القيمة NP وقتًا أسيًا." أولاً، هذا يعني أن P ≠ NP، وهو سؤال لا يزال غير محلول. علاوة على ذلك، تحتوي بعض المشكلات الكاملة ذات القيمة NP في الواقع على خوارزميات تعمل في وقت فائق الحدود، ولكن دون الأسي مثل O(2 ^{√ n} n ). على سبيل المثال، تكون مشكلات المجموعة المستقلة والمجموعة المهيمنة للرسوم البيانية المستوية كاملة ذات القيمة NP، ولكن يمكن حلها في وقت دون الأسي باستخدام نظرية الفاصل المستوي . ^[13]
"كل حالة من حالات مشكلة NP-complete صعبة." غالبًا ما يكون من السهل حل بعض الحالات، أو حتى أغلب الحالات، في غضون وقت متعدد الحدود. ومع ذلك، ما لم يكن P=NP، فإن أي خوارزمية في وقت متعدد الحدود يجب أن تكون خاطئة بشكل مقارب في أكثر من العديد من المدخلات الأسيّة ذات الحجم المعين. ^[14]
"إذا كانت قيمة P=NP، فمن الممكن كسر جميع الشفرات المشفرة." قد يكون حل مشكلة زمن الحدود أمرًا صعبًا للغاية في الممارسة العملية إذا كانت درجة الحدود أو ثوابتها كبيرة بما يكفي. بالإضافة إلى ذلك، توفر أمان نظرية المعلومات طرق تشفير لا يمكن كسرها حتى مع قوة الحوسبة غير المحدودة.
"سيكون الكمبيوتر الكمومي واسع النطاق قادرًا على حل المشكلات الكاملة ذات NP بكفاءة." تُعرف فئة مشكلات القرار التي يمكن حلها بكفاءة (من حيث المبدأ) بواسطة الكمبيوتر الكمومي المقاوم للأخطاء باسم BQP. ومع ذلك، لا يُعتقد أن BQP تحتوي على جميع NP، وإذا لم يكن الأمر كذلك، فلن تحتوي على أي مشكلة كاملة ذات NP. ^[15]

ملكيات

عند النظر إلى مشكلة القرار باعتبارها لغة رسمية في بعض الترميزات الثابتة، فإن مجموعة NPC لجميع مشاكل NP-complete ليست مغلقة تحت:

ليس من المعروف ما إذا كان NPC مغلقًا تحت التكامل ، نظرًا لأن NPC = co-NPC إذا وفقط إذا كان NP = co-NP ، ونظرًا لأن NP = co-NP هو سؤال مفتوح . ^[16]

انظر أيضا

مراجع

الاستشهادات

^ على سبيل المثال، يؤدي تعيين القيمة true لكل متغير إلى تحويل الاقتران الثامن عشر (وبالتالي الصيغة الكاملة) إلى false . ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$
^ كوبهام، آلان (1965). "الصعوبة الحسابية الجوهرية للوظائف". وقائع المنطق والمنهجية وفلسفة العلوم الجزء الثاني . شمال هولندا.
^ J. van Leeuwen (1998). Handbook of Theoretical Computer Science . Elsevier. ص 84. ISBN 978-0-262-72014-4.
^ J. van Leeuwen (1998). Handbook of Theoretical Computer Science . Elsevier. ص 80. ISBN 978-0-262-72014-4.
^ Kiersz, Andy. "عالم رياضيات بارز يدعي أنه حل أحد أعظم ألغاز الرياضيات — وهي واحدة من 6 مسائل بجائزة مليون دولار". Business Insider . تم الاسترجاع في 2023-04-24 .
^ تشن، جيانر؛ كانج، إياد أ؛ شيا، جي (2010-09-06). "تحسين الحدود العليا لغطاء الرأس". علوم الكمبيوتر النظرية . 411 (40): 3736-3756. doi : 10.1016/j.tcs.2010.06.026 . ISSN 0304-3975.
^ أجراوال، م .؛ أليندر، إي.؛ روديتش، ستيفن (1998). "التخفيضات في تعقيد الدائرة: نظرية التماثل ونظرية الفجوة". مجلة علوم الحاسب والنظام . 57 (2): 127-143. doi : 10.1006/jcss.1998.1583 . ISSN 1090-2724.
^ أجراوال، م .؛ أليندر، إي.؛ إمباجلياتزو، ر.؛ بيتاسي، ت .؛ روديتش، ستيفن (2001). "تقليل تعقيد الاختزالات". التعقيد الحسابي . 10 (2): 117-138. doi :10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.
^ دون كنوث ، تريسي لارابي، وبول م. روبرتس، الكتابة الرياضية المؤرشفة في 2010-08-27 على موقع واي باك مشين، § 25، ملاحظات الجمعية الأمريكية للرياضيات رقم 14 ، الجمعية الأمريكية للرياضيات، 1989 (كما هو الحال في تقرير ستانفورد الفني، 1987).
^ Knuth, DF (1974). "اقتراح مصطلحي". SIGACT News . 6 (1): 12–18. doi :10.1145/1811129.1811130. S2CID 45313676.
^ انظر الاستطلاع، أو [1] محفوظ في 2011-06-07 على موقع واي باك مشين .
^ بول، فيليب (2000). "كمبيوتر الحمض النووي يساعد بائعًا متجولًا". نيتشر . doi :10.1038/news000113-10.
^ برن (1990); دينيكو، كلينز وويجينجر (2006)؛ دورن وآخرون. (2005); ليبتون وتارجان (1980).
^ Hemaspaandra, LA; Williams, R. (2012). "SIGACT News Complexity Theory Column 76". ACM SIGACT News . 43 (4): 70. doi :10.1145/2421119.2421135. S2CID 13367514.
^ Aaronson, Scott (2010). "BQP and the polynomial hierarchy". في Schulman, Leonard J. (محرر). وقائع ندوة ACM الثانية والأربعين حول نظرية الحوسبة، STOC 2010، كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية، 5-8 يونيو 2010. رابطة آلات الحوسبة. ص. 141-150. arXiv : 0910.4698 . doi :10.1145/1806689.1806711. ISBN 978-1-4503-0050-6.
^ تالبوت، جون؛ ويلش، دي جيه إيه (2006)، التعقيد والتشفير: مقدمة، مطبعة جامعة كامبريدج، ص 57، ISBN 9780521617710إن مسألة ما إذا كان NP وco-NP متساويين هي على الأرجح ثاني أهم مشكلة مفتوحة في نظرية التعقيد، بعد مسألة P مقابل NP.

مصادر

جاري، مايكل ر .؛ جونسون، ديفيد س. (1979). أجهزة الكمبيوتر والتعقيد: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية (الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . رقم ISBN 9780716710455. السيد 0519066. OCLC 247570676.يعد هذا الكتاب كلاسيكيًا، إذ يطور النظرية، ثم يقوم بفهرسة العديد من مشاكل NP-Complete.
كوك، إس إيه (1971). "تعقيد إجراءات إثبات النظريات". وقائع ندوة رابطة مكائن الحوسبة السنوية الثالثة حول نظرية الحوسبة، رابطة مكائن الحوسبة، نيويورك . ص 151-158. doi : 10.1145/800157.805047 .
Dunne, PE "قائمة مُعلقة لمسائل NP-complete المختارة". COMP202، قسم علوم الكمبيوتر، جامعة ليفربول . تم الاسترجاع في 2008-06-21 .
كريسينزي، P .؛ كان، V.؛ هالدورسون، م.؛ كاربينسكي، م . ووجينجر، ج . “خلاصة وافية لمشاكل تحسين NP”. كيه تي إتش، ستوكهولم . تم الاسترجاع 2020-10-24 .
Dahlke, K. "NP-complete problems". مشروع مرجع الرياضيات . تم الاسترجاع في 2008-06-21 .
كارلسون، ر. "المحاضرة 8: مشاكل NP-complete" (PDF) . قسم علوم الكمبيوتر، جامعة لوند، السويد. مؤرشف من الأصل (PDF) في 19 أبريل 2009. تم الاسترجاع في 2008-06-21 .
Sun, HM "نظرية اكتمال NP". مختبر أمن المعلومات، قسم علوم الكمبيوتر، جامعة تسينغ هوا الوطنية ، مدينة هسينشو، تايوان. مؤرشف من الأصل (PPT) في 2009-09-02 . تم الاسترجاع في 2008-06-21 .
Jiang, JR "نظرية اكتمال NP" (PPT) . قسم علوم الكمبيوتر وهندسة المعلومات، الجامعة الوطنية المركزية ، مدينة جونجلي، تايوان . تم الاسترجاع في 2008-06-21 .
Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). "الفصل 34: اكتمال NP". مقدمة إلى الخوارزميات (الطبعة الثانية). MIT Press and McGraw-Hill. ص 966-1021. ISBN 978-0-262-03293-3.
Sipser, M. (1997). "Sections 7.4–7.5 (NP-completeness, Extra NP-complete Problems)" . مقدمة لنظرية الحوسبة . PWS Publishing. ص 248–271. ISBN 978-0-534-94728-6.
Papadimitriou, C. (1994). "الفصل 9 (مشاكل NP-complete)". التعقيد الحسابي (الطبعة الأولى). Addison Wesley. ص 181-218. ISBN 978-0-201-53082-7.
التعقيد الحسابي للألعاب والألغاز
تتريس صعبة، حتى التقريب
كاسحة الألغام هي لعبة NP-مكتملة!
بيرن، مارشال (1990). "خوارزميات أسرع وأكثر دقة لأشجار شتاينر في الشبكات المستوية". الشبكات . 20 (1): 109-120. doi :10.1002/net.3230200110..
Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006). "الخوارزميات الدقيقة لمشكلة دورة هاملتون في الرسوم البيانية المستوية". رسائل بحوث العمليات . 34 (3): 269-274. doi :10.1016/j.orl.2005.04.013..
دورن، فريدريك؛ بينينكس، إيلكو؛ بودلايندر، هانز إل ؛ فومين، فيدور ف. (2005). "خوارزميات دقيقة فعّالة على الرسوم البيانية المستوية: استغلال تحليلات الفروع المقطوعة للكرة". وقائع الندوة الأوروبية الثالثة عشرة حول الخوارزميات (ESA '05) . مذكرات محاضرات في علوم الكمبيوتر. المجلد 3669. دار نشر سبرينغر. ص 95-106. doi :10.1007/11561071_11. ISBN 978-3-540-29118-3..
ليبتون، ريتشارد جيه ؛ تارجان، روبرت إي. (1980). "تطبيقات نظرية الفاصل المستوي". مجلة سيام للحوسبة . 9 (3): 615-627. doi :10.1137/0209046. S2CID 12961628..

قراءة إضافية

سكوت آرونسون ، مشاكل NP-complete والواقع المادي ، ACM SIGACT News، المجلد 36، العدد 1. (مارس 2005)، ص 30-52.
لانس فورتنو ، حالة مشكلة P مقابل NP ، كوميون. إيه سي إم ، المجلد 52، العدد 9. (2009)، ص 78-86.

Original text

Rate this translation

Your feedback will be used to help improve Google Translate

[1] على سبيل المثال، يؤدي تعيين القيمة true لكل متغير إلى تحويل الاقتران الثامن عشر (وبالتالي الصيغة الكاملة) إلى false . ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$

[2] كوبهام، آلان (1965). "الصعوبة الحسابية الجوهرية للوظائف". وقائع المنطق والمنهجية وفلسفة العلوم الجزء الثاني . شمال هولندا.

[3] J. van Leeuwen (1998). Handbook of Theoretical Computer Science . Elsevier. ص 84. ISBN 978-0-262-72014-4.

[4] J. van Leeuwen (1998). Handbook of Theoretical Computer Science . Elsevier. ص 80. ISBN 978-0-262-72014-4.

[5] Kiersz, Andy. "عالم رياضيات بارز يدعي أنه حل أحد أعظم ألغاز الرياضيات — وهي واحدة من 6 مسائل بجائزة مليون دولار". Business Insider . تم الاسترجاع في 2023-04-24 .

[6] تشن، جيانر؛ كانج، إياد أ؛ شيا، جي (2010-09-06). "تحسين الحدود العليا لغطاء الرأس". علوم الكمبيوتر النظرية . 411 (40): 3736-3756. doi : 10.1016/j.tcs.2010.06.026 . ISSN 0304-3975.

[7] أجراوال، م .؛ أليندر، إي.؛ روديتش، ستيفن (1998). "التخفيضات في تعقيد الدائرة: نظرية التماثل ونظرية الفجوة". مجلة علوم الحاسب والنظام . 57 (2): 127-143. doi : 10.1006/jcss.1998.1583 . ISSN 1090-2724.

[8] أجراوال، م .؛ أليندر، إي.؛ إمباجلياتزو، ر.؛ بيتاسي، ت .؛ روديتش، ستيفن (2001). "تقليل تعقيد الاختزالات". التعقيد الحسابي . 10 (2): 117-138. doi :10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.

[9] دون كنوث ، تريسي لارابي، وبول م. روبرتس، الكتابة الرياضية المؤرشفة في 2010-08-27 على موقع واي باك مشين، § 25، ملاحظات الجمعية الأمريكية للرياضيات رقم 14 ، الجمعية الأمريكية للرياضيات، 1989 (كما هو الحال في تقرير ستانفورد الفني، 1987).

[10] Knuth, DF (1974). "اقتراح مصطلحي". SIGACT News . 6 (1): 12–18. doi :10.1145/1811129.1811130. S2CID 45313676.

[11] انظر الاستطلاع، أو [1] محفوظ في 2011-06-07 على موقع واي باك مشين .

[12] بول، فيليب (2000). "كمبيوتر الحمض النووي يساعد بائعًا متجولًا". نيتشر . doi :10.1038/news000113-10.

[13] برن (1990); دينيكو، كلينز وويجينجر (2006)؛ دورن وآخرون. (2005); ليبتون وتارجان (1980).

[14] Hemaspaandra, LA; Williams, R. (2012). "SIGACT News Complexity Theory Column 76". ACM SIGACT News . 43 (4): 70. doi :10.1145/2421119.2421135. S2CID 13367514.

[15] Aaronson, Scott (2010). "BQP and the polynomial hierarchy". في Schulman, Leonard J. (محرر). وقائع ندوة ACM الثانية والأربعين حول نظرية الحوسبة، STOC 2010، كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية، 5-8 يونيو 2010. رابطة آلات الحوسبة. ص. 141-150. arXiv : 0910.4698 . doi :10.1145/1806689.1806711. ISBN 978-1-4503-0050-6.

[16] تالبوت، جون؛ ويلش، دي جيه إيه (2006)، التعقيد والتشفير: مقدمة، مطبعة جامعة كامبريدج، ص 57، ISBN 9780521617710إن مسألة ما إذا كان NP وco-NP متساويين هي على الأرجح ثاني أهم مشكلة مفتوحة في نظرية التعقيد، بعد مسألة P مقابل NP.

ف ت هـ فئات التعقيد
يعتبر ممكنا	وقت الدلوغ التيار المتردد ⁰ مركز التحكم ⁰ تي سي ⁰ ل س ل رل فلوريدا هولندا اللغة الإنجليزية: كاملة كارولينا الشمالية SC نسخة ص P-كامل زد بي بي ار بي بي بي بي بى كيو بى أي بي إكس ف ب
مشتبه به غير قابل للتطبيق	أعلى ن ب NP-كامل NP-صعب مشارك في NP co-NP-كامل تي اف ان بي FNP أكون هيئة المتاحف القطرية الرقم الهيدروجيني ⊕ص ب ب #ص #P-كاملة الملكية الفكرية بي سبيس PSPACE-كاملة
يعتبر غير قابل للتنفيذ	الوقت المستغرق الوقت القادم مساحة اضافية 2-الوقت المستغرق ابتدائي العلاقات العامة ر يكرر الجميع
التسلسل الهرمي للطبقات	التسلسل الهرمي متعدد الحدود التسلسل الهرمي الأسي تسلسل هرمي لـ Grzegorczyk التسلسل الهرمي الحسابي التسلسل الهرمي المنطقي
عائلات الطبقات	دي تايم الوقت غير مناسب دي سبيس إن سبيس دليل قابل للتحقق احتماليًا نظام إثبات تفاعلي
قائمة فئات التعقيد