لماذا تسمى مشاكل NP بهذه الطريقة (و NP-Hard و NP-COMPLETE)؟

Question

حقًا .. أجرى الاختبار الأخير للتخرج يوم الثلاثاء ، وهذا أحد الأشياء التي لم أستطع فهمها أبدًا. أدرك أن الحل لمشكلة NP يمكن أن يكون في وقت متعدد الحدود. ولكن ما علاقة الحتمية بذلك؟
وإذا كان بإمكانك أن تشرح لي أين حصل NP-Complete و NP-Hard على أسمائهم ، فسيكون ذلك رائعًا (أنا متأكد تمامًا نكون).
آسف إذا كان هذا تافهاً ، لا يمكنني الحصول عليه (-:
شكرا لكم جميعا!

Answer 1

ص

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

NP

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

NP-Hard

فئة من المشكلات التي "على الأقل من الصعب مثل أصعب المشاكل في NP". بشكل رسمي ، هناك مشكلة في NP-Hard IFF ، هناك مشكلة في تكامل NP والتي تكون قابلة للتخفيض في وقت متعدد الحدود ؛ (أيضًا: IFF يمكن حلها في وقت متعدد الحدود بواسطة آلة Oracle مع أوراكل للمشكلة). من الواضح جدًا من أين يأتي الاسم.

NPC

فئة المشاكل التي هي NP وكذلك NP-HARD. فيما يتعلق بالتسمية ، حتى ويكيبيديا ليس متأكدًا من سبب اسمه كما هو.

Answer 2

لنبدأ بـ "nondeterministic". يمكن أن تكون آلة حتمية في حالة واحدة في وقت واحد. يمكننا أن نجعلهم في الواقع. الآلة غير المحددة هي بناء نظري يمكن أن يكون في أكثر من حالة واحدة في وقت واحد. (هناك أوجه تشابه مع الحوسبة الكمومية هنا ، ولكن لأغراضنا هنا ، إنها مضللة. تجاهلها.)

إذا كنا نريد حل مشكلة في آلة حتمية ، فإننا نبدأها ، ومرتفع سلسلة من الخطوات لمحاولة العثور على مشكلة. إذا قمنا بتصميم جهاز غير محدد ، فيمكنه أن يمر بجميع سلسلة الخطوات الممكنة في نفس الوقت.

مجموعة المشاكل التي سنشعر بها هي مشاكل القرار: بالنظر إلى بيان المشكلة ، إما أن يكون هناك حل أم لا. ابحث عن حل أو تقرير أنه لا يوجد شيء. على سبيل المثال ، افترض أن لديك مجموعة من العبارات المنطقية: A أو لا B أو B أو D أو D أو NOND أو A أو B ، .... بالنظر إلى مجموعة تعسفية ، هل يمكنك العثور على قيم الحقيقة لجميع المتغيرات مثل أن جميع العبارات صحيحة؟

الآن ، دعونا نفكر في P. لنفترض أننا نمثل حجم المشكلة بواسطة n. يمكن أن يكون الحجم هو عدد المدن في مشكلة بائع السفر ، وعدد البيانات المنطقية في المشكلة أعلاه ، أيا كان. بالنظر إلى N n ، ستتطلب المشكلة قدرًا معينًا من الموارد لحلها على نظام معين. الآن ، إذا مضاعفة الموارد أو القدرة الحسابية ، فماذا يحدث لحجم المشكلة التي يمكننا حلها؟ إذا كانت المشكلة ذات تعقيد متعدد الحدود ، مما يعني في P ، فإن الحجم يرتفع بكسر معين. قد يتضاعف ، أو يرتفع بنسبة 40 ٪ ، أو 10 ٪. في المقابل ، إذا كان من التعقيد الأسي ، فإن الحجم يرتفع برقم معين. إننا نفكر عمومًا في مشاكل p على أنها مشكلات قابلة للحل وأسية غير قابلة للحل لأن المشكلات تصبح كبيرة ، على الرغم من أن هذا تبسيط. من وجهة نظر غير رسمية ، فإن التعقيد متعدد الحدود هو القدرة على معرفة الأمور حول المشكلة بالتتابع ، في حين أن الأسي يجب أن ينظر إلى جميع المجموعات الممكنة.

لنفترض أنه يمكننا حل المشكلة في الوقت متعدد الحدود على آلة حتمية. تكمن المشكلة في P. لنفترض أنه يمكننا حلها في وقت متعدد الحدود على آلة غير محددة ، وهو نفس الشيء مثل القدرة على التحقق من الحل المقترح في الوقت متعدد الحدود على آلة حتمية. ثم المشكلة في NP. الحيلة هنا هي أننا لا نستطيع صنع آلات حقيقية غير محددة ، بحيث لا تعني حقيقة أن المشكلة في NP من العملي حلها.

الآن إلى NP-Complete. جميع المشاكل في P في NP. بالنسبة للمشكلات A و B في NP ، قد نكون قادرين على القول أنه إذا كان A في P ، فهذا هو B. يتم ذلك من خلال إيجاد طريقة لإعادة صياغة B كنوع من المشكلة. إن مشكلة NP-Complete هي أحد ، إذا كانت في P ، فإن كل مشكلة في NP موجودة في P. كما قد تخمن ، إيجاد طريقة لإعادة صياغة كل مشكلة ممكنة لأن مشكلة معينة لم تكن سهلة ، وسأفعل ذلك فقط قل أن مشكلة البيانات المنطقية أعلاه (مشكلة الرضا) كانت الأولى التي تم تأكيدها NP. بعد ذلك كان الأمر أسهل ، لأنه كان من الضروري فقط إثبات أنه إذا كانت المشكلة C في P ، فقد كانت الرضا.

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

هناك مشاكل لا تتناسب مع هذا القالب. مشكلة البائع المتجول ، كما تم طرحها عادة ، هي العثور على أرخص مسار يربط جميع المدن. هذه ليست مشكلة في القرار ، ولا يمكننا التحقق من أي حل مقترح مباشرة. يمكننا إعادة صياغة الأمر كمشكلة قرار: بالنظر إلى تكلفة C ، هل هناك طريق أرخص من C؟ هذه المشكلة مكتملة NP ، ومع القليل من العمل ، يمكننا حل TSP الأصلي بسهولة مثل الشكل المعدل ، NP-COMPLETE ،. لذلك ، فإن TSP هو np-hard ، لأنه على الأقل صعب مثل مشكلة NP-Complete.

Answer 3

يسمى NP NP (وقت متعدد الحدود غير المحدود) لأنه يمكن حل مشكلة NP في وقت متعدد الحدود بواسطة آلة تورينج غير محددة.

Answer 4

لنبدأ بـ NP: في NP ، N مخصص لـ "nondeterministic" و P هو "وقت متعدد الحدود". إنها فئة المشكلات التي يمكن حلها في وقت متعدد الحدود إذا كان لديك آلة تورينج غير محددة يمكنها التفرع في كل دورة لاستكشاف إمكانيات بالتوازي (أصبح "التحقق من الحل" الشائع في الآونة الأخيرة ولكنه لا يوضح ذلك ماذا يعني "N"). يمكن مقارنة الآلة غير المحددة بجهاز كمبيوتر متوازي مع عدد لا حصر له من المعالجات ، والقدرة على ذلك fork() في كل تعليمات.

إن القول بأن مشكلة Q هي "np-hard" يعني أنه يمكن تقليل أي مشكلة في NP إلى مشكلة Q (في الوقت متعدد الحدود). نظرًا لأن العلاقة "يمكن تخفيضها إلى" بين المشكلات هي علاقة ترتيب ، يمكنك التفكير في "NP-Hard" كمعنى "على الأقل بنفس القدر مثل جميع مشاكل NP".

إن مشكلة "NP-Complete" هي ببساطة واحدة من المشكلات في NP التي هي NP-Hard. أعتقد أن فئة المشاكل تحتاج إلى اسم ، لكنني لست متأكدًا من كيفية شرح اختيار كلمة "كاملة".

Answer 5

ولكن ما علاقة الحتمية بذلك؟

من ويكيبيديا:

NP هي مجموعة من جميع مشاكل القرار التي يكون لدى "نعم" من أجلهم أدلة يمكن التحقق منها بكفاءة عن حقيقة أن الإجابة هي بالفعل "نعم". بتعبير أدق ، يجب التحقق من هذه الأدلة في وقت متعدد الحدود بواسطة أ حتمية آلة تورينج

لست متأكدا من تاريخ الأسماء على الرغم من. تحرير: لدي تخمين رغم ذلك. ما يلي هو التكهنات لكنني لا أعتقد أنه غير معقول.

NP-HARD هي أي مشكلة على الأقل صعبة مثل أصعب المشاكل في NP. لذلك ، يمكن القول أن المشكلة المعنية سيكون لها صلابة NP. ، وبالتالي NP-Hard.

إذا كان يمكن حل أي مشكلة واحدة في NP-Complete بسرعة ، فيمكن أيضًا حل كل مشكلة في NP بسرعة. لذلك ، يمكن حل مجموعة كاملة من مشاكل NP.

EDIT2: ويكيبيديا كاملة (التعقيد) تشير المقالة إلى:

تكتمل المشكلة الحسابية لفئة التعقيد إذا كانت ، بمعنى رسمي ، واحدة من المشكلات "الأصعب" أو "الأكثر تعبيرية" في فئة التعقيد