اكتمال NP

في نظرية التعقيد الحسابي ، تُعدّ مسائل NP-complete أصعب المسائل التي يمكن التحقق من حلولها بسرعة . وبشكل أدق، تكون المسألة NP-complete عندما:

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

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

غالبًا ما يُشار إلى مجموعة مسائل NP-complete بالرمز NP-C أو NPC .

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

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

مشكلة اتخاذ القرار${\displaystyle \scriptstyle C}$تكون المسألة من فئة NP-كاملة إذا:

1. ${\displaystyle \scriptstyle C}$يقع في NP، و
2. كل مشكلة في NP قابلة للاختزال إلى${\displaystyle \scriptstyle C}$في وقت متعدد الحدود. ^{[ 2 ] [ 3 ]}

${\displaystyle \scriptstyle C}$يمكن إثبات أن المسألة تنتمي إلى فئة NP من خلال إثبات أن أحد الحلول المرشحة لـ${\displaystyle \scriptstyle C}$يمكن التحقق من ذلك في وقت متعدد الحدود.

تُصنَّف مسألة القرار القابلة للحل في وقت متعدد الحدود ضمن الفئة P. جميع المسائل في P تنتمي بالضرورة إلى الفئة NP. مع ذلك، لم يُثبت بعد أن الفئة NP أكبر من P. بعبارة أخرى، لا يُعرف حتى الآن ما إذا كانت هناك مسائل في NP لا تنتمي إلى P. تُعرف مسألة تساوي الفئتين P وNP بمسألة P مقابل NP . من نتائج تعريف اكتمال NP أنه إذا كان لدينا خوارزمية ذات وقت متعدد الحدود (على آلة تورينج المجردة ، أو أي آلة مجردة أخرى مكافئة لتورينج ) لـ${\displaystyle \scriptstyle C}$، يمكننا حل جميع المشاكل في فئة NP في وقت متعدد الحدود.

تُصنَّف المسألة على أنها صعبة الحل من فئة NP إذا أمكن تحويل جميع عناصر فئة NP إليها في وقت متعدد الحدود، حتى وإن لم تكن تنتمي إلى هذه الفئة. ^{[ 4 ]} وتُصنَّف المسألة على أنها كاملة الحل من فئة NP إذا كانت تنتمي إلى فئة NP وصعبة الحل من فئة NP في الوقت نفسه. وبالتالي، تُعتبر المسائل الكاملة الحل من فئة NP، بمعنى ما، أصعب المسائل في فئة NP.

تنص نظرية كوك-ليفين على أن مسألة إرضاء المعادلات المنطقية هي مسألة كاملة من فئة NP، مما يثبت لأول مرة وجود مثل هذه المسائل. في عام 1972، أثبت ريتشارد كارب أن العديد من المسائل الأخرى هي أيضًا مسائل كاملة من فئة NP (انظر مسائل كارب الـ 21 الكاملة من فئة NP )؛ وبالتالي، توجد فئة من المسائل الكاملة من فئة NP، إلى جانب مسألة إرضاء المعادلات المنطقية. منذ هذه النتائج الأصلية، تم إثبات أن آلاف المسائل الأخرى كاملة من فئة NP عن طريق اختزالها من مسائل أخرى سبق إثبات أنها كاملة من فئة NP؛ وقد جُمع العديد من هذه المسائل في كتاب غاري وجونسون (1979) .

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

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

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

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

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

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

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

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

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

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

طُرح مفهوم اكتمال NP في عام 1971 (انظر نظرية كوك-ليفين )، بينما استُخدم مصطلح NP-complete لاحقًا. في مؤتمر STOC عام 1971 ، دار نقاش حاد بين علماء الحاسوب حول إمكانية حل مسائل NP-complete في وقت متعدد الحدود على آلة تورينغ حتمية . وقد توصل جون هوبكروفت إلى إجماع بين الحضور على تأجيل البت في مسألة إمكانية حل مسائل NP-complete في وقت متعدد الحدود إلى وقت لاحق، نظرًا لعدم وجود براهين رسمية تدعم أيًا من الادعاءات.

أعلن معهد كلاي للرياضيات أن مسألة P مقابل NP هي واحدة من مسائل جائزة الألفية السبع في عام 2000. ^{[ 8 ] [ 9 ]}

بحسب دونالد كنوث ، شاع استخدام مصطلح "NP-complete" بفضل ألفريد أهو وجون هوبكروفت وجيفري أولمان في كتابهم الشهير "تصميم وتحليل خوارزميات الحاسوب". ويشير إلى أنهم أدخلوا هذا التغيير في براهين النسخة التجريبية للكتاب (من "polynomially-complete")، بناءً على نتائج استطلاع رأي أجراه بين أوساط علوم الحاسوب النظرية . ^{[ 10 ]} وتضمنت الاقتراحات الأخرى التي وردت في الاستطلاع ^{[ 11 ]} مصطلحات مثل " Herculean " و"formidable" و "hard-boiled" الذي أطلقه ستيغليتز تكريمًا لكوك، واختصار شين لين "PET" الذي يرمز إلى "probably exponential time"، ولكن اعتمادًا على نتيجة مسألة P مقابل NP ، يمكن أن يرمز إلى " provably exponential time" أو "previously exponential time". ^{[ 12 ]}

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

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

إذا نظرنا إلى مشكلة القرار كلغة رسمية في ترميز ثابت، فإن مجموعة NPC لجميع المشاكل الكاملة من فئة NP ليست مغلقة في ظل:

• الاتحاد
• تقاطع
• سلسلة
• كلين ستار

ليس من المعروف ما إذا كانت NPC مغلقة تحت المكمل ، لأن NPC = co-NPC إذا وفقط إذا كان NP = co-NP ، ولأن NP = co-NP مسألة مفتوحة . ^{[ 17 ]}

• شبه مكتمل
• أداة (علوم الحاسوب)
• نظرية لادنر
• قائمة مسائل NP-كاملة
• NP-hard
• مشكلة P = NP
• NP-كاملة بقوة
• بائع متجول (فيلم 2012)