ما هي مشاكل NP؟

Question

قرأت المقال عن ويكيبيديا ، لكنني لم أستطع فهم ما هي مشكلات NP بالضبط. هل يمكن لأي شخص أن يخبرني عنهم وأيضًا ما هي العلاقة بينهم بمشاكل P؟

Answer 1

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

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

لقد اخترت عمدا أمثلة موجودة في NP وليس في P (أي مشكلة يصعب العثور على الحل) حتى تتمكن من فهم الفرق. من السهل أيضًا التحقق من جميع المشكلات التي يسهل حلها ، فقط حلها ومقارنتها. وهذا هو ، p هي مجموعة فرعية من NP.

Answer 2

ليست إجابة حقًا ، لأن رابط Piccolo أكثر فائدة ، لكن باحث HP يدعي أنه أثبت P! = NP ، إليك الورقة.

www.hpl.hp.com/personal/vinay_deolalikar/papers/pnp12pt.pdf

لم يتم قبول ذلك بعد ، لكني أتمنى له حظًا سعيدًا بمبلغ 1 مليون دولار.