صعوبة NP

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
مخطط أويلر لمجموعة مسائل P و NP و NP-complete و NP-hard.
مخطط أويلر لمجموعة مسائل P و NP و NP-كاملة و NP-صعبة. الجانب الأيسر صحيح بافتراض أن P≠NP ، بينما الجانب الأيمن صحيح بافتراض أن P=NP (باستثناء أن اللغة الفارغة ومكملتها ليستا أبدًا NP-كاملة).

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

من الأمثلة البسيطة على المسائل الصعبة من نوع NP مسألة مجموع المجموعات الفرعية .

بصورة غير رسمية، إذا كانت المسألة H من المسائل الصعبة من فئة NP، فإن حلها لا يقل صعوبة عن حل المسائل في فئة NP . ومع ذلك، فإن العكس ليس صحيحًا: فبعض المسائل غير قابلة للتقرير ، وبالتالي فهي أصعب حلًا من جميع المسائل في فئة NP، ولكنها على الأرجح ليست من المسائل الصعبة من فئة NP (إلا إذا كانت P=NP). [ 5 ]

تعريف

تُعتبر مسألة القرار H مسألة صعبة من نوع NP عندما يكون لكل مسألة L في NP، يوجد اختزال متعدد الحدود من L إلى H في وقت متعدد الحدود . [ 1 ] : 80

تعريف آخر هو اشتراط وجود اختزال زمني متعدد الحدود من مسألة NP-كاملة G إلى H. [ 1 ] : 91 بما أن أي مسألة L في NP تختزل زمنيًا متعدد الحدود إلى G ، فإن L تختزل بدورها إلى H زمنيًا متعدد الحدود، لذا فإن هذا التعريف الجديد يستلزم التعريف السابق. ولا يقتصر هذا التعريف على مسائل NP-صعبة، بل يشمل أيضًا مسائل البحث أو مسائل التحسين .

عواقب

إذا كانت P ≠ NP، فلا يمكن حل المشكلات الصعبة من نوع NP في وقت متعدد الحدود.

يمكن تقريب بعض مسائل التحسين الصعبة من نوع NP في زمن متعدد الحدود حتى نسبة تقريب ثابتة (خاصةً تلك الموجودة في APX ) أو حتى أي نسبة تقريب (تلك الموجودة في PTAS أو FPTAS ). توجد فئات عديدة من قابلية التقريب، كل منها يُمكّن من التقريب حتى مستوى مختلف. [ 6 ]

أمثلة

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

توجد مسائل قرار صعبة الحل (NP-hard) ولكنها ليست كاملة الحل (NP-complete) ، مثل مسألة التوقف . وهي المسألة التي تسأل: "إذا أُعطي برنامجٌ ما ومدخلاته، فهل سيستمر في العمل إلى الأبد؟" هذا سؤال إجابته نعم / لا ، وبالتالي فهو مسألة قرار. من السهل إثبات أن مسألة التوقف صعبة الحل (NP-hard) ولكنها ليست كاملة الحل (NP-complete). على سبيل المثال، يمكن اختزال مسألة إرضاء الصيغ المنطقية إلى مسألة التوقف بتحويلها إلى وصف لآلة تورينج تُجرّب جميع قيم الصواب ، وعندما تجد قيمة تُحقق الصيغة تتوقف، وإلا فإنها تدخل في حلقة لا نهائية. من السهل أيضًا ملاحظة أن مسألة التوقف ليست في فئة NP، لأن جميع المسائل في فئة NP قابلة للحل في عدد محدود من العمليات، ولكن مسألة التوقف، بشكل عام، غير قابلة للحل . وهناك أيضًا مسائل صعبة الحل (NP-hard) ليست كاملة الحل (NP-complete) ولا غير قابلة للحل . على سبيل المثال، يمكن تحديد لغة الصيغ البوليانية الكمية الحقيقية في فضاء متعدد الحدود ، ولكن ليس في وقت متعدد الحدود غير حتمي (إلا إذا كانت NP = PSPACE ). [ 8 ]

اصطلاح تسمية NP

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

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

مجالات التطبيق

غالباً ما يتم التعامل مع المشكلات الصعبة من نوع NP باستخدام لغات تعتمد على القواعد في مجالات تشمل:

المسائل الصعبة من نوع NP

غالباً ما تكون المشكلات القابلة للتقرير ولكنها ليست من فئة NP-complete هي مشكلات تحسين:

انظر أيضاً

مراجع

  1. 1 2 3 ليوين، جان فان ، محرر. (1998). دليل علوم الحاسوب النظرية . المجلد  أ، الخوارزميات والتعقيد. أمستردام: إلسيفير. ISBN 0262720140. OCLC 247934368 . 
  2. ↑ كنوت، دونالد (1974). "ملاحظة ختامية حول مسائل NP-hard". أخبار ACM SIGACT . 6 (2): 15-16 . doi : 10.1145/1008304.1008305 . S2CID 46480926 . 
  3. ^ دانييل بيير بوفيه. بييرلويجي كريسينزي (1994). مقدمة لنظرية التعقيد . برنتيس هول. ص. 69. ردمك  0-13-915380-2.
  4. ↑ "Shtetl-Optimized » أرشيف المدونة » الحجة العلمية لـ P≠NP" . www.scottaaronson.com . 7 مارس 2014. تاريخ الاسترجاع: 25 سبتمبر 2016 .  
  5. ↑ "هل تُعدّ المسائل غير القابلة للتقرير (المكملة لـ R) مجموعة فرعية من المسائل الصعبة من نوع NP؟" . موقع تبادل المعلومات في علوم الحاسوب . تم الاطلاع عليه بتاريخ 9 فبراير 2024 .
  6. ↑ إسكوفيه، ب.؛ باشوس، ب.ث. (2010). "دراسة استقصائية حول بنية فئات التقريب". مراجعة علوم الحاسوب . 4 (1): 19-40 . doi : 10.1016/j.cosrev.2009.11.001 .
  7. ↑ لولر، إي إل ؛ لينسترا، جيه كيه ؛ رينوي كان، إيه إتش جي؛ شمويز، دي بي (1985)، مسألة البائع المتجول: جولة إرشادية في التحسين التوافقي ، جون وايلي وأولاده، رقم ISBN 0-471-90413-9.
  8. ↑ بتعبير أدق، هذه اللغة كاملة من فئة PSPACE ؛ انظر، على سبيل المثال، Wegener, Ingo (2005)، نظرية التعقيد: استكشاف حدود الخوارزميات الفعالة ، Springer، ص 189، ISBN  9783540210450.