NP (التعقيد)

مشكلة لم تُحل في علوم الحاسوب

${\displaystyle {\mathsf {P\ {\overset {?}{=}}\ NP}}}$

المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

في نظرية التعقيد الحسابي ، تُعدّ NP ( الوقت متعدد الحدود غير الحتمي ) فئة تعقيد تُستخدم لتصنيف مسائل القرار . NP هي مجموعة مسائل القرار التي تكون فيها حالات المسألة ، حيث تكون الإجابة "نعم"، قابلة للتحقق من البراهين في وقت متعدد الحدود بواسطة آلة تورينغ حتمية ، أو بديلًا لذلك، هي مجموعة المسائل التي يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينغ غير حتمية . ^{[ 2 ] [ ملاحظة 1 ]}

• NP هي مجموعة مسائل القرار التي يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينج غير حتمية .
• NP هي مجموعة مسائل القرار التي يمكن التحقق منها في وقت متعدد الحدود بواسطة آلة تورينج حتمية .

التعريف الأول هو أساس الاختصار NP؛ أي " غير حتمي ، ذو زمن متعدد الحدود". هذان التعريفان متكافئان لأن الخوارزمية القائمة على آلة تورينج تتكون من مرحلتين، الأولى تتضمن تخمينًا للحل، يتم توليده بطريقة غير حتمية، بينما تتضمن المرحلة الثانية خوارزمية حتمية تتحقق مما إذا كان التخمين حلاً للمسألة. ^{[ 3 ]}

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

ترتبط فئة التعقيد NP بفئة التعقيد co-NP ، والتي يمكن التحقق من إجابتها "لا" في وقت متعدد الحدود. ويُعدّ تحديد ما إذا كانت NP = co-NP أم لا سؤالًا آخرًا بارزًا في نظرية التعقيد. ^{[ 5 ]}

يمكن تعريف فئة التعقيد NP بدلالة NTIME على النحو التالي:

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k}),}$

أين${\displaystyle {\mathsf {NTIME}}(n^{k})}$هي مجموعة مسائل القرار التي يمكن حلها بواسطة آلة تورينج غير حتمية في${\displaystyle O(n^{k})}$وقت.

بصورة مكافئة، يمكن تعريف NP باستخدام آلات تورينج الحتمية كمُدقِّقات. تكون اللغة L في NP إذا وفقط إذا وُجدت كثيرتا حدود p و q ، وآلة تورينج حتمية M ، بحيث

• بالنسبة لجميع قيم x و y ، تعمل الآلة M في زمن p (| x |) عند إدخال ⁠${\displaystyle (x,y)}$⁠ .
• لكل x في L ، يوجد تسلسل y طوله q (| x |) بحيث${\displaystyle M(x,y)=1}$⁠ .
• لكل x ليس في L ولكل سلسلة y بطول q (| x |) ،${\displaystyle M(x,y)=0}$⁠ .

تتضمن فئة NP العديد من مشاكل علوم الحاسوب ، مثل إصدارات القرار للعديد من مشاكل البحث والتحسين.

تُعتبر مجموعة NP مغلقة تحت عمليات الاتحاد والتقاطع والتسلسل ونجمة كلين والانعكاس . ولا يُعرف ما إذا كانت مجموعة NP مغلقة تحت عملية المتمم (هذا السؤال هو ما يُسمى بسؤال "NP مقابل co-NP") .

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

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

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

التعريفان لمصطلح NP، باعتباره فئة المسائل التي يمكن حلها بواسطة آلة تورينغ غير حتمية في وقت متعدد الحدود، وفئة المسائل التي يمكن التحقق منها بواسطة آلة تورينغ حتمية في وقت متعدد الحدود، متكافئان. وقد وُصف البرهان في العديد من الكتب الدراسية، على سبيل المثال، كتاب سيبسر " مقدمة في نظرية الحوسبة" ، القسم 7.3.

لتوضيح ذلك، لنفترض أولًا أن لدينا مُدقِّقًا حتميًا. يمكن لآلة غير حتمية ببساطة تشغيل المُدقِّق بشكل غير حتمي على جميع سلاسل البراهين الممكنة (يتطلب هذا عددًا من الخطوات متعدد الحدود فقط، لأنه يمكنه اختيار الحرف التالي في سلسلة البراهين بشكل غير حتمي في كل خطوة، ويجب أن يكون طول سلسلة البراهين محدودًا متعدد الحدود). إذا كان أي برهان صحيحًا، فسيتم قبوله؛ أما إذا لم يكن أي برهان صحيحًا، فإن السلسلة ليست ضمن اللغة وسيتم رفضها.

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

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

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

تُعرَّف فئة NP باستخدام الآلات الحتمية فقط. إذا سمحنا للمُدقِّق بأن يكون احتماليًا (مع ذلك، ليس بالضرورة أن يكون آلة BPP ^{[ 6 ]} )، فسنحصل على فئة MA قابلة للحل باستخدام بروتوكول آرثر-ميرلين دون أي اتصال بين آرثر وميرلين.

العلاقة بين BPP و NP غير معروفة: فليس من المعروف ما إذا كانت BPP مجموعة جزئية من NP ، أو ما إذا كانت NP مجموعة جزئية من BPP ، أو لا هذه ولا تلك. إذا كانت NP مُحتواة في BPP ، وهو أمرٌ يُعتبر مستبعدًا لأنه سيستلزم حلولًا عملية لمسائل NP-كاملة ، فإن NP = RP و PH ⊆ BPP . ^{[ 7 ]}

NP هي فئة من مسائل القرار ؛ والفئة المماثلة من مسائل الدوال هي FNP .

الاستثناءات الصارمة الوحيدة المعروفة تأتي من نظرية التسلسل الهرمي الزمني ونظرية التسلسل الهرمي المكاني ، وهما على التوالي${\displaystyle {\mathsf {NP\subsetneq NEXPTIME}}}$و${\displaystyle {\mathsf {NP\subsetneq EXPSPACE}}}$.

من حيث نظرية التعقيد الوصفي ، فإن NP تتوافق بدقة مع مجموعة اللغات التي يمكن تعريفها بواسطة منطق الرتبة الثانية الوجودي ( نظرية فاجين ).

يمكن اعتبار NP نوعًا بسيطًا جدًا من أنظمة الإثبات التفاعلية ، حيث يُقدّم المُثبت شهادة الإثبات، بينما يقوم المُدقّق، وهو آلة حتمية تعمل في زمن متعدد الحدود، بفحصها. وهو نظام كامل لأن وجود سلسلة إثبات صحيحة يجعله مقبولًا، وسليم لأن المُدقّق لا يمكنه القبول في حال عدم وجود سلسلة إثبات مقبولة.

من أهم نتائج نظرية التعقيد أن فئة NP تُعرَّف بأنها المشكلات التي يمكن حلها باستخدام براهين قابلة للتحقق احتماليًا، حيث يستخدم المُدقِّق عددًا عشوائيًا من البتات مقداره O(log n ) ويفحص عددًا ثابتًا فقط من بتات سلسلة البرهان (الفئة PCP (log n , 1)). بعبارة أخرى، يمكن استبدال مُدقِّق NP المذكور أعلاه بمُدقِّق آخر يُجري فحصًا عشوائيًا لبعض المواضع في سلسلة البرهان، وباستخدام عدد محدود من رميات العملة، يمكنه تحديد الإجابة الصحيحة باحتمالية عالية. وهذا يسمح بإثبات العديد من النتائج المتعلقة بصعوبة خوارزميات التقريب .

• آلة تورينج – نموذج حسابي يحدد آلة مجردة 

• توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7القسم 34.2: التحقق في وقت متعدد الحدود، الصفحات  979-983 .
• مايكل سيبسر (1997). مقدمة في نظرية الحوسبة . دار نشر PWS. رقم ISBN 0-534-94728-X.الأقسام 7.3 – 7.5 (فئة NP، اكتمال NP، مشاكل NP الكاملة الإضافية)، الصفحات  241 – 271.
• ديفيد هاريل ، يشاي فيلدمان . الخوارزميات: روح الحوسبة، أديسون ويسلي، ريدينغ، ماساتشوستس، الطبعة الثالثة، 2004.

• حديقة حيوانات التعقيد : NP
• مقدمة من مجلة "أمريكان ساينتست" حول أبحاث نظرية التعقيد التقليدية والحديثة: "الخوارزميات العرضية"