ما هي الاختلافات بين NP، NP-Complete و NP-Hard؟

Question

ما هي الاختلافات بين NP., np-complete. و NP-Hard.?

أنا على علم بالعديد من الموارد في جميع أنحاء الويب. أود أن أقرأ تفسيراتك، والسبب هو أنهم قد يختلفون عن ما هناك، أو هناك شيء لا أعرفه.

Answer 1

أفترض أنك تبحث عن تعريفات بديهية، لأن التعاريف التقنية تتطلب بعض الوقت لفهمها. بادئ ذي بدء، دعونا نتذكر مفهوم مطلوبا أوليا لفهم هذه التعريفات.

• مشكلة القرار: مشكلة مع نعم أو لا إجابه.

---

الآن، دعونا نحدد تلك فصول التعقيد.

ب

P هو فئة تعقيد تمثل مجموعة من جميع مشاكل القرار التي يمكن حلها في وقت متعدد الحدود.

وهذا هو، بالنظر إلى مثيل المشكلة، يمكن تحديد الجواب نعم أو لا يمكن تحديده في وقت متعدد الحدود.

مثال

إعطاء الرسم البياني المتصل G, ، هل يمكن أن تكون رؤوسها ملونة باستخدام لونين بحيث لا توجد حافة أحادية اللون؟

الخوارزمية: ابدأ بسؤال تعسفي، لونها حمراء وكل جيرانها الأزرق والمتابعة. توقف عند نفاد القمم أو إجبارك على جعل حافة تحتوي على نقاط النهاية نفس اللون.

---

NP.

NP عبارة عن فئة تعقيد تمثل مجموعة من مشاكل القرارات التي تحتوي على الحالات التي تكون فيها الإجابة "نعم" دليلا يمكن التحقق منها في وقت متعدد الحدود.

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

مثال

العدد الصحيح في NP. هذه هي المشكلة التي تعطى أعداد صحيحة n و m, ، هل هناك عدد صحيح f مع 1 < f < m, ، مثل ذلك f الانقسامات n (f هو عامل صغير n)?

هذه مشكلة في القرار لأن الإجابات هي نعم أو لا. إذا أيدي شخص ما مثيل للمشكلة (لذلك يدينون الولايات المتحدة الأعداد الصحيحة n و m) وعدد صحيح f مع 1 < f < m, ، وادع ذلك f هو عامل n (الشهادة)، يمكننا التحقق من الإجابة في وقت البولينمال عن طريق أداء الشعبة n / f.

---

np-complete.

NP-Complete هو فئة التعقيد التي تمثل مجموعة من جميع المشاكل X في NP التي من الممكن الحد من أي مشكلة NP أخرى Y ل X في الوقت متعدد الحدود.

وهذا يعني هذا يعني أننا نستطيع حلها Y بسرعة إذا كنا نعرف كيفية حل X بسرعة. على وجه التحديد، Y غير متاخ X, ، إذا كان هناك خوارزمية زمنية متعددة الحدود f لتحويل المثيلات y من Y للحالات x = f(y) من X في الوقت متعدد الحدود، مع الممتلكات التي الإجابة y نعم، إذا وفقط إذا كانت الإجابة على f(y) هو نعم.

مثال

3-SAT. وبعد هذه هي المشكلة التي نحتاج فيها للتزامن (ands) من 3 شرق (ORS)، بيانات النموذج

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

حيث كل x_vij هو متغير منطقي أو نفي متغير من قائمة محددة مسبقا (x_1, x_2, ... x_n).

يمكن أن تظهر ذلك يمكن تقليل كل مشكلة NP إلى 3-SAT. وبعد دليل هذا هو التقنية ويتطلب استخدام التعريف الفني ل NP (بناء على آلات تورينج غير حتمية). هذا هو المعروف باسم نظرية كوك.

ما يجعل مشاكل NP-Complete مهمة هو أنه في حالة العثور على خوارزمية وقت متعدد الحدود الحتمية لحل أحدهم، فإن كل مشكلة NP قابلة للحل في وقت متعدد الحدود (مشكلة واحدة لحكم عليها جميعا).

---

NP-Hard.

بشكل حدسي، هذه هي المشاكل التي هي على الأقل صعوبة في مشاكل NP. وبعد لاحظ أن مشاكل NP-Hard لا يجب أن تكون في NP, ، و ليس لديهم مشاكل في القرار.

التعريف الدقيق هنا هو ذلك مشكلة X هو NP-Hard، إذا كان هناك مشكلة كاملة NP Y, ، مثل ذلك Y غير متاخ X في وقت متعدد الحدود.

ولكن نظرا لأن أي مشكلة كاملة من NP يمكن تخفيضها إلى أي مشكلة أخرى كاملة من NP في الوقت متعدد الحدود، فيمكن تخفيض جميع المشكلات الكاملة من NP إلى أي مشكلة صعبة NP في وقت متعدد الحدود. ثم، إذا كان هناك حلا لمشكلة NP-الصعبة في الوقت متعدد الحدود، فهناك حلا لجميع مشاكل NP في وقت متعدد الحدود.

مثال

ال إيقاف المشكلة هي مشكلة صعبة NP. هذه هي المشكلة التي تعطى برنامج P وإدخال I, ، هل توقف؟ هذه مشكلة في القرار ولكنها ليست في NP. من الواضح أن أي مشكلة كاملة من NP يمكن تخفيضها إلى هذا واحد. كمثال آخر، أي مشكلة NP كاملة هي NP-Hard.

مشكلة NP المفضل لدي هي مشكلة minesweper..

---

ص = NP.

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

من الواضح أن P هي مجموعة فرعية من NP. السؤال المفتوح هو ما إذا كانت مشاكل NP لها حلول محددة أو زمن متعدد الحدود. يعتقد إلى حد كبير أنهم لا. فيما يلي مقالة حديثة رائعة حول الأحدث (وأهمية) مشكلة P = NP: حالة P مشكلة IPSUS.

أفضل كتاب حول هذا الموضوع هو أجهزة الكمبيوتر والحقولية بقلم جاري وجونسون.

Answer 2

لقد كنت أتطلع حول ورؤية العديد من التفسيرات الطويلة. إليك مخطط صغير قد يكون مفيدا لتلخيصه:

لاحظ مدى صعوبة الزيادات من أعلى إلى أسفل: أي يمكن تخفيض NP إلى NP-Complete, ، وأي NP-Complete يمكن تخفيضها إلى NP-Hard, ، كل ذلك في وقت p (متعدد الحدود).

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

____________________________________________________________ | نوع المشكلة | يمكن التحقق منه في P في الوقت | قابلة للحل في وقت طن | زيادة صعوبة _______________________________________________________________ | | | ص | نعم | نعم | | | NP |. نعم | نعم أو لا * | | | NP-Complete | نعم | غير معروف | | | NP-Hard | نعم أو لا ** | غير معروف *** | | ____________________________________________________________ الخامس

الملاحظات على Yes أو No إدخالات:

• * مشكلة NP هي أيضا ص هو قابل للحل في أطول وقت.
• ** مشكلة NP-الصعبة هي أيضا NP-Complete غير قابلة للتحقق في وقت.
• *** قد تكون مشاكل NP كاملة (كل ما تشكل مجموعة فرعية من NP-Hard). بقية NP الصعبة ليست كذلك.

أنا أيضا وجدت هذا المخطط مفيد للغاية في رؤية كيف تتوافق كل هذه الأنواع مع بعضها البعض (إيلاء المزيد من الانتباه إلى النصف الأيسر من الرسم البياني).

Answer 3

هذه إجابة غير رسمية للغاية على السؤال المطروح.

يمكن كتابة 3233 كمنتج لشخصين آخرين أكبر من 1؟ هل هناك أي طريقة للمشي المسار حول كل من سبع جسور Königsberg دون أخذ أي جسر مرتين؟ هذه أمثلة على الأسئلة التي تشارك سمة شائعة. قد لا يكون من الواضح كيفية تحديد الإجابة بكفاءة، ولكن إذا كانت الإجابة هي "نعم"، فهناك دليل قصير وسريع للتحقق من الدليل. في الحالة الأولى عامل غير تافه من 51؛ في الثانية، طريقا للمشي في الجسور (تركيب القيود).

أ مشكلة القرار هي مجموعة من الأسئلة مع نعم أو لا إجابات تختلف فقط في معلمة واحدة. قل مشكلة مركب = {"هو n مركب": n هو عدد صحيح} أو eulerpath = {"يفعل الرسم البياني G هل لديك مسار Euler؟ ": G هو الرسم البياني المحدود}.

الآن، بعض مشاكل القرار تضفي أنفسهم فعال، إن لم تكن واضحة الخوارزميات. اكتشف Euler خوارزمية فعالة لمشاكل مثل "الجسور السبع ل Königsberg" منذ أكثر من 250 عاما.

من ناحية أخرى، بالنسبة للعديد من مشاكل القرار، ليس من الواضح كيفية الحصول على الإجابة - ولكن إذا كنت تعرف بعض المعلومات الإضافية، فمن الواضح كيف تذهب حول الإثبات التي حصلت عليها الحق. المركب هو مثل هذا: شعبة التجربة هي الخوارزمية الواضحة، وهي بطيئة: إلى العامل رقم 10 أرقام، عليك أن تجرب شيئا مثل 100000 من المقسورات المحتملة. ولكن إذا، على سبيل المثال، قال لك شخص ما أن 61 هو مقسوم من 3233، وهو قسم طويل بسيط هو وسيلة فعالة لرؤية أنها صحيحة.

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

يستمر البحث في الخوارزميات، يتم إنشاء خوارزميات جديدة ذكية جديدة طوال الوقت. مشكلة قد لا تعرف كيفية حلها اليوم بكفاءة قد تتحول إلى حل فعال (إن لم يكن واضحا) غدا. في الواقع، استغرق الأمر الباحثين حتى 2002 للعثور على حل فعال للمركبة! مع كل هذه التقدم، يتعين على المرء أن يتساءل: هل هذا قليلا عن وجود براهين قصيرة فقط وهم؟ يمكن كل مشكلة القرار التي تضفي نفسها على البراهين الفعالة حلا فعالا؟ لا أحد يعرف.

ولعل أكبر مساهمة في هذا المجال جاءت مع اكتشاف فئة غريبة من مشاكل NP. من خلال اللعب مع نماذج الدائرة للحساب، وجد ستيفن كوك مشكلة اتخاذ قرار من مجموعة متنوعة NP التي كانت ذات صعبة أو أصعب من كل مشكلة NP أخرى. حل فعال ل مشكلة استيفاء منطقية يمكن استخدامها لإنشاء حل فعال ل اي شيء اخر مشكلة في NP. بعد فترة وجيزة، أظهر ريتشارد كربا أن عددا من مشاكل القرارات الأخرى يمكن أن تخدم نفس الغرض. هذه المشاكل، بمعنى مشاكل "أصعب" في NP، تعرف باسم np-complete. مشاكل.

بالطبع، NP ليست سوى فئة من مشاكل القرارات. العديد من المشاكل غير مذكورة بشكل طبيعي بهذه الطريقة: "ابحث عن عوامل n"، ابحث عن أقصر المسار في الرسم البياني الذي يزور كل قسط "،" إعطاء مجموعة من المهام المتغيرة التي تجعل التعبير المنطقي التالي صحيح ". على الرغم من أن المرء قد يتحدث بشكل غير رسمي عن بعض المشاكل هذه يجري "في NP"، من الناحية الفنية لا معنى لها - فهي ليست مشاكل في القرار. قد يكون لبعض هذه المشكلات نفس الطاقة مثل مشكلة NP-Complete: من شأن حلا فعالا لهذه المشكلات (عدم اتخاذ القرار) يؤدي مباشرة إلى حل فعال لأي مشكلة NP. مشكلة مثل هذا يسمى NP-Hard..

Answer 4

بالإضافة إلى الإجابات الرائعة الأخرى، ها هي مخطط نموذجي يستخدم الأشخاص لإظهار الفرق بين NP، NP-Complete، و NP-Hard:

Answer 5

ص (وقت متعدد الحدود): كما يوحي الاسم نفسه، هذه هي المشاكل التي يمكن حلها في الوقت متعدد الحدود.

NP (الوقت غير الحاسم متعدد الحدود): هذه هي مشاكل القرار التي يمكن التحقق منها في الوقت متعدد الحدود. هذا يعني، إذا كنت تدعي أن هناك حل زمني متعدد الحدود لمشكلة معينة، فأنت تطلب مني إثبات ذلك. بعد ذلك، سأقدم لك دليلا يمكنك التحقق منه بسهولة في وقت متعدد الحدود. هذه النوع من المشاكل تسمى مشاكل NP. لاحظ أننا هنا لا نتحدث عن ما إذا كان هناك حل زمني متعدد الحدود لهذه المشكلة أم لا. لكننا نتحدث عن التحقق من الحل لمشكلة معينة في وقت متعدد الحدود.

NP-Hard: هذه على الأقل بجد باعتبارها أصعب مشاكل في NP. إذا استطعنا حل هذه المشكلات في الوقت متعدد الحدود، فيمكننا حل أي مشكلة NP التي يمكن أن تكون موجودة. لاحظ أن هذه المشاكل ليست بالضرورة مشاكل NP. هذا يعني، قد نستطيع / قد تحقق من الحل لهذه المشاكل في وقت متعدد الحدود.

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

Answer 6

أسهل طريقة لشرح P V. NP وما دون الدخول إلى التقنيات هي مقارنة "مشاكل الكلمات" مع "مشاكل الاختيار متعددة".

عندما تحاول حل "مشكلة كلمة"، عليك أن تجد الحل من الصفر. عندما تحاول حل "مشاكل متعددة الخيارات"، لديك خيار: إما أن يحلها كما تريد "مشكلة كلمة"، أو حاول توصيل كل من الإجابات التي تعطى لك، واختيار الإجابة المرشحة التي تناسبها.

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

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

جوهر P V. NP هو السؤال: "هل هناك أي مشاكل سهلة الاختيار من متعدد ليست سهلة مثل مشاكل كلمة"؟ وهذا هو، هل هناك مشاكل من السهل التحقق من صحة إجابة معينة ولكن العثور على أن الإجابة من الصفر أمر صعب؟

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

أخيرا، مشاكل NP كاملة هي تلك التي هي في وقت واحد NP و NP-Hard. بعد القياس لدينا، فهي في وقت واحد "سهلة مثل مشاكل متعددة الخيارات" و "أصعب كل من مشاكل كلمة".

Answer 7

أعتقد أننا نتمكن من الإجابة عليها أكثر إيجازية. أجبت أ سؤال ذي صلة, ونسخ جوابي من هناك

ولكن أولا، مشكلة NP-الصعبة هي مشكلة لا يمكننا إثبات أن حل زمن متعدد الحدود موجود. عادة ما يثبت صلابة NP من بعض "المشكلة-P" عن طريق تحويل مشكلة صعبة مثبتة بالفعل إلى "مشكلة P" في الوقت متعدد الحدود.

للإجابة على بقية السؤال، تحتاج أولا إلى فهم المشكلات الصعبة NP هي أيضا NP-Complete. إذا كانت المشكلة الصعبة NP تنتمي إلى تعيين NP، فهي كاملة NP. للانتماء إلى مجموعة NP، يجب أن تكون مشكلة

(ط) مشكلة في القرار،
(2) يجب أن يكون عدد الحلول للمشكلة محدودة ويجب أن يكون كل حل من طول متعدد الحدود، و
(3) بالنظر إلى حل طول متعدد الحدود، يجب أن نكون قادرين على القول ما إذا كانت الإجابة على المشكلة هي نعم / لا

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

Answer 8

مشاكل NP كاملة هي تلك المشاكل التي تعد كل من NP-Hard وفي فئة التعقيد NP. لذلك، لإظهار أن أي مشكلة معينة هي np-complete، تحتاج إلى إظهار أن المشكلة في كل من NP وأنها صلبة NP.

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

مثال على حل غير محدد لمشكلة K-Clique سيكون مثل:

1) حدد عشوائيا العقد K من الرسم البياني

2) تحقق من أن هذه العقد K تشكل زمرة.

الاستراتيجية المذكورة أعلاه هي متعدد الحدود في حجم الرسم البياني للإدخال وبالتالي فإن مشكلة K-Clique هي في NP.

لاحظ أن جميع المشكلات للحتمية للحتمية في الوقت متعدد الحدود هي أيضا في NP.

إظهار أن المشكلة هي NP-Hard عادة ما تنطوي على تخفيض من بعض المشكلات الصعبة الأخرى لمشكلتك باستخدام تعيين وقت متعدد الحدود: http://en.wikipedia.org/wiki/reduction_(complexity)

Answer 9

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

بالنسبة لشخص يعتقد أن التعقيد الحسابي هو فقط حوالي P و NP، هنا هو الموارد الأكثر شمولة حول مشاكل التعقيد الحاسوبية المختلفة. بصرف النظر عن المشكلات التي طرحها OP، أدرجت حوالي 500 فئة مختلفة من المشاكل الحسابية بأوصاف لطيفة وأيضا قائمة الأوراق البحثية الأساسية التي تصف الفصل.

Answer 10

كما أفهمها، NP-Hard. المشكلة ليست "أصعب" من np-complete. مشكلة. في الواقع، بحكم التعريف، كل مشكلة NP كاملة هي:

1. في NP.
2. NP-Hard.

- مقدمة. إلى الخوارزميات (3ED) من قبل Cormen، Leiserson، Rivest، وشتاين، PG 1069

Answer 11

العثور على بعض defintion مثير للاهتمام: