NP هي فئة اللغات التي تحتوي على أدوات التحقق من الوقت متعددة الحدود
يعد الفصل NP، الذي يرمز إلى "الزمن متعدد الحدود غير المحدد"، مفهومًا أساسيًا في نظرية التعقيد الحسابي، وهو مجال فرعي من علوم الكمبيوتر النظرية. لفهم NP، يجب على المرء أولاً فهم مفهوم مشاكل القرار، وهي أسئلة ذات إجابة بنعم أو لا. تشير اللغة في هذا السياق إلى مجموعة من السلاسل فوق بعض الحروف الأبجدية، حيث تقوم كل سلسلة بتشفير مثال لمشكلة القرار.
يقال أن اللغة (L) موجودة في NP إذا كان هناك مدقق زمني متعدد الحدود لـ (L). أداة التحقق عبارة عن خوارزمية حتمية (V) تأخذ مدخلين: مثيل (x) وشهادة (y). تُعرف الشهادة (y) أيضًا باسم "الشاهد" أو "الدليل". يتحقق المدقق (V) مما إذا كانت الشهادة (y) تؤكد أن (x) تنتمي إلى اللغة (L). رسميًا، تكون اللغة (L) في NP إذا كان هناك خوارزمية متعددة الحدود (V) ومتعددة الحدود (p(n)) بحيث أنه لكل سلسلة (x في L)، توجد سلسلة (y) مع ( |y|.leq p(|x|)) و (V(x, y) = 1). على العكس من ذلك، لكل سلسلة (x notin L)، لا توجد سلسلة (y) بحيث (V(x, y) = 1).
لتوضيح هذا المفهوم، فكر في مشكلة "الإشباع المنطقي" (SAT) المعروفة. تتساءل مشكلة SAT عما إذا كان هناك تعيين لقيم الحقيقة للمتغيرات في صيغة منطقية معينة بحيث يتم تقييم الصيغة على أنها صحيحة. مشكلة SAT موجودة في NP لأنه، في حالة وجود صيغة منطقية ( phi ) وتعيين ( alpha ) لقيم الحقيقة لمتغيراتها، يمكن للمرء التحقق في وقت متعدد الحدود مما إذا كانت ( alpha ) تفي بـ ( phi ). هنا، المثال ( x ) هو الصيغة المنطقية ( phi )، والشهادة ( y ) هي المهمة ( alpha ). يتحقق المدقق ( V ) مما إذا كانت ( alpha ) تجعل ( phi ) صحيحًا، وهو ما يمكن القيام به في وقت متعدد الحدود فيما يتعلق بحجم ( phi ).
مثال توضيحي آخر هو مشكلة "مسار هاميلتون". تسأل هذه المشكلة عما إذا كان هناك مسار في رسم بياني معين يزور كل قمة مرة واحدة بالضبط. مشكلة المسار الهاملتوني موجودة أيضًا في NP لأنه، بالنظر إلى الرسم البياني (G) وتسلسل القمم (P)، يمكن للمرء التحقق في زمن متعدد الحدود مما إذا كان (P) هو مسار هاميلتوني في (G). في هذه الحالة، المثال ( x ) هو الرسم البياني ( G ) والشهادة ( y ) هي تسلسل القمم ( P ). يتحقق المدقق ( V ) مما إذا كان ( P ) يشكل مسارًا هاميلتونيًا، وهو ما يمكن إجراؤه في زمن متعدد الحدود فيما يتعلق بحجم ( G ).
إن مفهوم إمكانية التحقق في زمن كثير الحدود مهم لأنه يوفر طريقة لوصف المشكلات التي يمكن التحقق منها بكفاءة، حتى لو كان العثور على الحل قد يكون غير قابل للتطبيق حسابيًا. وهذا يؤدي إلى السؤال الشهير عما إذا كان (P = NP)، والذي يسأل عما إذا كان كل مشكلة يمكن التحقق من حلها في زمن كثير الحدود يمكن حلها أيضًا في زمن كثير الحدود. تتكون الفئة (P) من مشكلات القرار التي يمكن حلها في زمن كثير الحدود بواسطة آلة تورنج حتمية. إذا كان (P = NP)، فهذا يعني أن كل مشكلة لها مُتحقق في زمن كثير الحدود لها أيضًا مُحلل في زمن كثير الحدود. يظل هذا السؤال أحد أهم المشكلات المفتوحة في علوم الكمبيوتر.
إحدى الخصائص الرئيسية لـ NP هي أنها مغلقة تحت تخفيضات زمنية متعددة الحدود. إن تقليل وقت متعدد الحدود من لغة ( L_1 ) إلى لغة ( L_2 ) هو دالة قابلة للحساب ( f ) بحيث ( x في L_1 ) إذا وفقط إذا ( f(x) في L_2 ). إذا كان هناك اختزال زمني متعدد الحدود من ( L_1 ) إلى ( L_2 ) و ( L_2 ) في NP، فإن ( L_1 ) يكون أيضًا في NP. هذه الخاصية مفيدة في دراسة اكتمال NP، والتي تحدد المشاكل "الأصعب" في NP. تكون المشكلة NP-كاملة إذا كانت في NP ويمكن اختزال كل مشكلة في NP إليها في زمن متعدد الحدود. كانت مشكلة SAT أول مشكلة تم إثبات اكتمالها NP، وهي بمثابة أساس لإثبات اكتمال NP للمسائل الأخرى.
لمزيد من توضيح مفهوم إمكانية التحقق من الزمن متعدد الحدود، فكر في مشكلة "مجموع المجموعة الفرعية". تسأل هذه المشكلة عما إذا كانت هناك مجموعة فرعية من مجموعة معينة من الأعداد الصحيحة التي تجمع قيمة هدف محددة. مشكلة مجموع المجموعة الفرعية موجودة في NP لأنه، في ضوء مجموعة من الأعداد الصحيحة ( S ) وقيمة مستهدفة ( t ) ومجموعة فرعية ( S' ) من ( S ) ، يمكن للمرء التحقق في زمن كثير الحدود ما إذا كان مجموع العناصر في ( س ' ) يساوي ( ر ). هنا، المثيل ( x ) هو الزوج ( (S, t) )، والشهادة ( y ) هي المجموعة الفرعية ( S' ). يتحقق المدقق (V) مما إذا كان مجموع العناصر في (S') يساوي (t)، وهو ما يمكن إجراؤه في زمن متعدد الحدود فيما يتعلق بحجم (S).
تتجاوز أهمية إمكانية التحقق في زمن متعدد الحدود الاعتبارات النظرية. فمن الناحية العملية، يعني هذا أنه بالنسبة للمشكلات في NP، إذا تم تقديم حل مقترح (شهادة)، فيمكن التحقق منه بكفاءة. وهذا له آثار كبيرة على بروتوكولات التشفير، ومشاكل التحسين، والعديد من المجالات حيث يكون التحقق من صحة الحل مهمًا.
لتلخيص ذلك، تشمل فئة NP مشاكل القرار التي يمكن التحقق من الحل المقترح لها في زمن متعدد الحدود بواسطة خوارزمية حتمية. يعد هذا المفهوم أساسيًا في نظرية التعقيد الحسابي وله آثار عميقة على الجوانب النظرية والعملية لعلوم الكمبيوتر. لا تزال دراسة NP، وقابلية التحقق من الزمن متعدد الحدود، والمفاهيم ذات الصلة مثل اكتمال NP، مجالًا بحثيًا حيويًا وحاسمًا.
أسئلة وأجوبة أخرى حديثة بخصوص تعقيد:
- هل فئة PSPACE لا تساوي فئة EXPSPACE؟
- هل فئة التعقيد P هي مجموعة فرعية من فئة PSPACE؟
- هل يمكننا إثبات أن فئة Np وP متماثلتان من خلال إيجاد حل متعدد الحدود فعال لأي مشكلة كاملة NP على TM حتمية؟
- هل يمكن أن تكون فئة NP مساوية لفئة EXPTIME؟
- هل هناك مشاكل في PSPACE لا توجد لها خوارزمية NP معروفة؟
- هل يمكن أن تكون مشكلة SAT مشكلة NP كاملة؟
- هل يمكن أن تكون المشكلة في فئة التعقيد NP إذا كانت هناك آلة تورينج غير حتمية يمكنها حلها في زمن متعدد الحدود
- هل P و NP في الواقع نفس فئة التعقيد؟
- هل كل لغة خالية من السياق في فئة التعقيد P؟
- هل هناك تناقض بين تعريف NP كفئة من مشاكل القرار مع أدوات التحقق من الوقت متعدد الحدود وحقيقة أن المشاكل في الفئة P لها أيضًا أدوات التحقق من الوقت متعدد الحدود؟
عرض المزيد من الأسئلة والأجوبة في التعقيد