ما هو NP-كامل في علوم الكمبيوتر؟

Question

ما هي مشكلة NP-Complete؟لماذا هو موضوع مهم في علوم الكمبيوتر؟

Answer 1

NP تمثل غير حتمية متعدد الحدود وقت.

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

الشيء الرئيسي الذي يجب استخلاصه من مسألة NP-Complete هو أنه لا يمكن حلها في زمن متعدد الحدود بأي طريقة معروفة.NP-Hard/NP-Complete هي طريقة لإظهار أن فئات معينة من المشكلات غير قابلة للحل في وقت واقعي.

يحرر:كما لاحظ آخرون، غالبًا ما تكون هناك حلول تقريبية لمشاكل NP-Complete.في هذه الحالة، عادةً ما يعطي الحل التقريبي حدودًا تقريبية باستخدام ترميز خاص يخبرنا بمدى قرب التقريب.

Answer 2

ما هو NP?

NP هي مجموعة الكل مشاكل القرار (الأسئلة التي تكون الإجابة عليها بنعم أو لا) والتي يمكن أن تكون الإجابات بـ "نعم". تم التحقق في زمن كثير الحدود (O(n^ك) أين ن هو حجم المشكلة، و ك ثابت) بواسطة أ آلة تورينج الحتمية.يستخدم الوقت متعدد الحدود أحيانًا كتعريف سريع أو بسرعة.

ما هو ص?

P هي مجموعة جميع مسائل القرار التي يمكن حلها تم حلها في وقت البولينمال بواسطة أ آلة تورينج الحتمية.نظرًا لأنه يمكن حلها في زمن كثير الحدود، فيمكن أيضًا التحقق منها في زمن كثير الحدود.ولذلك فإن P هي مجموعة فرعية من NP.

ما هو NP-كامل?

المشكلة x الموجودة في NP موجودة أيضًا في NP-Complete إذا وفقط إذا يمكن حل كل مشكلة أخرى في NP بسرعة (على سبيل المثال.في زمن كثير الحدود) تحولت إلى x.

بعبارة أخرى:

1. x موجود في NP، و
2. كل مشكلة في NP هي قابل للاختزال إلى العاشر

إذن ما الذي يجعل NP-كامل ومن المثير للاهتمام أنه إذا تم حل أي من مشكلات NP-Complete بسرعة، فسيتم حل كل شيء NP يمكن حل المشاكل بسرعة.

انظر أيضا هذا المنصب ما هو "P=NP؟"، ولماذا هو سؤال مشهور؟

ما هو NP-صعب?

NP-Hard هي مشاكل لا تقل صعوبة عن أصعب المشكلات في NP.لاحظ أن مشكلات NP-Complete هي أيضًا مشكلات NP-hard.ومع ذلك، ليست كل المشاكل الصعبة NP هي NP (أو حتى مشكلة قرار)، على الرغم من وجودها NP كبادئة.هذا هو NP في NP-الصلب لا يعني زمن متعدد الحدود غير حتمي.نعم، هذا أمر محير، لكن استخدامه راسخ ومن غير المرجح أن يتغير.

Answer 3

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

1. يوجد دليل زمني متعدد الحدود لكل حالة من المشكلة بإجابة "نعم" أن الإجابة هي "نعم" أو (ما يعادلها)
2. توجد خوارزمية متعددة الحدود (ربما تستخدم متغيرات عشوائية) لها احتمال غير صفري للإجابة على "نعم" إذا كانت الإجابة على مثيل المشكلة هي "نعم" وستقول "لا" 100 ٪ من الوقت إذا الجواب هو "لا". بمعنى آخر ، يجب أن يكون للخوارزمية معدل سلبي كاذب أقل من 100 ٪ وليس إيجابيات كاذبة.

المشكلة X هي NP-Complete إذا

1. X موجود في NP، و
2. بالنسبة لأي مشكلة Y في NP، هناك "تخفيض" من Y إلى X:خوارزمية زمنية متعددة الحدود تقوم بتحويل أي مثيل لـ Y إلى مثيل X بحيث تكون الإجابة على مثيل Y هي "نعم" إذا وفقط إذا كانت الإجابة على مثيل X هي "نعم".

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

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

Answer 4

NP-Complete هي فئة من المشاكل.

الفصل P يتكون من تلك المشاكل التي يمكن حلها وقت البولينمال.على سبيل المثال، يمكن حلها في O(n^ك) لبعض k ثابت، حيث ن هو حجم الإدخال.ببساطة، يمكنك كتابة البرنامج الذي سيتم تشغيله معقول وقت.

الفصل NP يتكون من تلك المشاكل التي يمكن التحقق منها في زمن متعدد الحدود.أي أنه إذا حصلنا على حل محتمل، فيمكننا التحقق مما إذا كان الحل المعطى صحيحًا في زمن متعدد الحدود.

بعض الأمثلة هي الرضا المنطقي (أو قعد) مشكلة، أو مشكلة دورة هاميلتون.هناك العديد من المشكلات المعروفة بوجودها في الفصل NP.

NP-Complete يعني المشكلة على الأقل بجد مثل أي مشكلة في NP.

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

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

Answer 5

والأساس يمكن تصنيف المشاكل هذا العالم ك

1) مشكلة غير قابلة للحل 2) مشكلة مستعصية 3) NP-مشكلة 4) P-مشكلة

---

1) أول واحد هو عدم وجود حل لهذه المشكلة. 2) والثاني هو الحاجة الوقت الأسي (وهذا هو O (2 ^ ن) أعلاه). ويسمى 3) والثالث على NP. 4) والرابعة هي سهلة المشكلة.

---

وP: يشير إلى حل لمشكلة متعدد الحدود الوقت

.

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

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

وNP الصلب: يشير متعدد الحدود الوقت لم يتم بعد التوصل إلى حل، ولكن من المؤكد أنها غير قادرة على التحقق منها في الوقت متعدد الحدود. مشكلة NP الصلب تفوق صعوبة مجلس الشعب.

Answer 6

وانها فئة من المشاكل حيث يجب علينا محاكاة كل إمكانية للتأكد لدينا الحل الأمثل.

وهناك الكثير من الاستدلال جيدة لبعض المشاكل NP-كاملة، لكنها ليست سوى تكهنا في أحسن الأحوال.

Answer 7

إذا كنت تبحث عن مثال لمشكلة NP-كاملة ثم أقترح عليك أن نلقي نظرة على 3-SAT .

ووالفرضية الأساسية هي أن يكون لديك تعبير في حرف عطف طبيعي النموذج ، الذي هو وسيلة ل يقول لديك مجموعة من التعبيرات انضم اليهم نسب الأرجحية أن كل شيء يجب أن يكون صحيحا:

(a or b) and (b or !c) and (d or !e or f) ...

والمشكلة 3-SAT هو العثور على حل يرضي التعبير حيث كل من OR-تعبيرات وبالضبط 3 القيم المنطقية في المباراة:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

وهناك حل لهذا يمكن للمرء أن يكون (أ = T، ب = T، ج = F، د = F). ومع ذلك، فقد تم اكتشاف أي الخوارزمية التي سوف نحل هذه المشكلة في الحالة العامة في الوقت متعدد الحدود. ما يعنيه هذا هو أن أفضل طريقة لحل هذه المشكلة هو أن تفعل أساسا القوة الغاشمة تخمين والاختيار ومحاولة مجموعات مختلفة حتى تجد أحد أن يعمل.

ما هو خاص حول المشكلة 3-SAT هو أن أي مشكلة NP-كاملة يمكن خفضها الى مشكلة 3-سبت وهذا يعني أنه إذا كان يمكنك العثور على خوارزمية الوقت متعدد الحدود إلى حل هذه المشكلة ثم تحصل 1،000،000 $ ، ناهيك عن احترام وتقدير علماء الحاسوب والرياضيات في جميع أنحاء العالم.

Answer 8

وبصراحة، قد يكون ويكيبيديا أفضل مكان للبحث عن إجابة لهذا.

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

Answer 9

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

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

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

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

Answer 10

والتعاريف لمشاكل NP كاملة أعلاه هو الصحيح، ولكن ظننت أنني قد الشمع غنائية حول أهميتها الفلسفية كما لا أحد قد تناولت هذه المسألة حتى الآن.

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

ولكن ليس كل تضيع اذا كانت هناك مشكلة سوف تواجه هي NP كاملة. وهناك مجال واسع والتقني جدا حيث الناس دراسة خوارزميات التقريب، والتي سوف تعطيك ضمانات لكونها قريبة إلى حل مشكلة كاملة NP. بعض هذه هي ضمانات قوية بشكل لا يصدق - على سبيل المثال، ل3sat، يمكنك الحصول على ضمانة 7/8 من خلال خوارزمية واضحة حقا. حتى أفضل، في الواقع، هناك بعض الاستدلال قوية جدا، والتي تتفوق في إعطاء إجابات كبيرة (ولكن لا ضمانات!) لهذه المشاكل.

لاحظ أن مشكلتين مشهورة جدا - تشاكل المخططات والعوملة - ليست معروفة لتكون P أو NP.

Answer 11

لقد سمعت تفسيرًا ، أي: "إن اكتمال NP هو على الأرجح أحد الأفكار الأكثر غموضًا في دراسة الخوارزميات.يشير "NP" إلى "زمن متعدد الحدود غير محدد"، وهو اسم لما يسمى فئة التعقيد التي يمكن أن تنتمي إليها المشاكل.المهم بخصوص NP فئة التعقيد هي أن المشاكل داخل تلك الفئة يمكن أن تكون تم التحقق بواسطة خوارزمية زمنية متعددة الحدود.على سبيل المثال، النظر في مشكلة عد الأشياء.لنفترض أن هناك مجموعة من التفاح على الطاولة.المشكلة هي "كم عدد التفاح هناك؟" يتم تزويدك بإجابة محتملة ، 8.يمكنك التحقق من هذه الإجابة في وقت متعدد الحدود باستخدام خوارزمية عد التفاح.يتم عد التفاحات في زمن O(n) (هذا هو تدوين Big-oh)، لأنه يستغرق خطوة واحدة لحساب كل تفاحة.بالنسبة لـ n من التفاح، تحتاج إلى n من الخطوات.هذه المشكلة موجودة في فئة التعقيد NP.

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

والمثال الكلاسيكي لمشكلة NP-Complete هو مشكلة البائع المتجول."

المؤلف:apoxybutt من: http://www.everything2.com/title/NP-Complete

Answer 12

مشكلة NP :-

1. مشكلة NP هي مشكلة يمكن حلها في زمن متعدد الحدود غير حتمي.
2. تعمل الخوارزمية غير الحتمية على مرحلتين.
3. مرحلة التخمين غير الحتمي && مرحلة التحقق غير الحتمي.

نوع مشكلة Np

1. NP كاملة
2. NP الثابت

مشكلة NP كاملة :-

1. مشكلة القرار أ تسمى NP كاملة إذا كانت تحتوي على الخاصيتين التاليتين:-

1. انها تنتمي إلى فئة NP.
2. يمكن تحويل كل مشكلة أخرى في NP إلى P في زمن متعدد الحدود.

بعض السابقين :-

• مشكلة الحقيبة
• مشكلة مجموع المجموعة الفرعية
• مشكلة تغطية قمة الرأس

Answer 13

مشاكل

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

Answer 14

ومشكلة NP هي واحدة حيث يمكن إنشاء خوارزمية الكمبيوتر الذي يتحقق حل في الوقت متعدد الحدود.

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

وحتى الحصول على crackin ".