P = توضيح NP

Question

لنستخدم البائع المتجول كمثال، إلا إذا كنت تعتقد أن هناك مثالًا أبسط وأكثر قابلية للفهم.

ما أفهمه من سؤال P=NP هو أنه بالنظر إلى الحل الأمثل لمشكلة صعبة، فمن السهل التحقق من الإجابة، ولكن من الصعب جدًا العثور على الحل.

مع البائع المتجول، نظرًا لأقصر طريق، من الصعب أيضًا تحديد أنه أقصر طريق، لأنه يتعين عليك حساب كل طريق للتأكد من أن هذا الحل هو الأمثل.

هذا لا معنى له.إذن ما الذي أفتقده؟أتخيل أن الكثير من الأشخاص الآخرين يواجهون خطأً مماثلاً في فهمهم عندما يتعلمون عن هذا الأمر.

Answer 1

إصدار TSP الخاص بك هو في الواقع NP-Hard، بالضبط لأسباب تذكر.من الصعب التحقق من أنه الحل الصحيح.إصدار TSP الذي هو NP-Complete هو إصدار القرار من المشكلة (نقلا عن Wikipedia):

href="https://en.wikipedia.org/wiki/travelling_salesman_problem" rel="noreferrer"> إصدار القرار من TSP (حيث إعطاء طول L، المهمة هي أن تقرر ما إذا كان الرسم البياني لديهتنتمي جولة في معظم L) إلى فئة مشاكل NP كاملة.

بمعنى آخر، بدلا من السؤال "ما هو أقصر طريق ممكن من خلال الرسم البياني TSP؟"، نحن نسأل "هل هناك طريق من خلال الرسم البياني TSP يناسب ميزانيتي؟".

Answer 2

هناك الكثير من الإجابات اللائقة هنا ولكن لا شيء لا يملح زوجين سوء فهم مهم إلى حد ما يبدو أن لديك.

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

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

ولكن هناك بعض المشاكل في NP نعتقد أنها من الصعب حلها. المبالغة قليلا، ونحن نسمي مشاكل NP كاملة. (لاحظ أن هذه لا تزال يجب أن تكون مشاكل في القرار). يمكننا أن نقول مشكلة أ على الأقل أنها صعبة مثل المشكلة (ب) إذا، فإننا نفترض أن لدينا OracleBox نوراكل يحل المشكلة أ بوضوح، إذا كنت تستطيع حل مشكلة التحسين (التي تحصل على الحل الأمثل)، فيمكنك حل مشكلة القرار. وبالتالي فإن مشكلة التحسين هي بجد على الأقل مشكلة في اتخاذ القرار المقابل. إذا أظهرنا أن إصدار مشكلة القرار من TSP هو NP-Complete (الذي هو)، فإننا نعرف أن مشكلة تبديل الأمثل هي أيضا صعبة مثل مشاكل NP-Complete، لكنها ليست في الواقع np-complete لأنها ليست كذلك مشكلة في القرار. ندعو هذه المشاكل NP-Hard.

Answer 3

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

مثال على إصدار مشكلة القرار في TSP هو "بالنظر إلى مجموعة من المدن والمسافات بين المدن، هل هناك جولة بطول إجمالي أقل من $ك$؟"، أين $ك$ هو ثابت محدد في المثيل.والنتيجة هي "نعم" أو "لا".وفي كلتا الحالتين لا تؤدي الإجابة إلى التحقق السريع من صحة الإجابة.

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

• حدد أن الجولة المقترحة هي في الواقع جولة -- تزور جميع المدن وتعبر فقط الطرق الموجودة بين المدن (أحيانًا "ذات مسافات محدودة" عندما يقوم المرء بتشفير المسارات المفقودة على أنها ذات طول $\إنفتي$).
• إذا كان الأمر كذلك، فحدد أن طول المسار أقصر من الثابت $ك$ في حالة المشكلة.

لا توفر إجابة "نعم" أو "لا" جولة مقترحة.

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

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

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

Answer 4

NP هو كل شيء عن مشاكل القرار - مشاكل حيث الجواب هو "نعم" أو "لا".

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

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

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

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

Answer 5

أجد أنه من السهل فهمه باستخدام مشكلة 3-SAT NP كاملة

هناك $ n $ المتغيرات المنطقية ويمكنك أن تقرر لكل منها إما أن يتم تعيين $ true $ أو $ FALSE $ القيمة وأنت تعطى $ k $ clauses. تحتوي كل من البنود على 3 متغيرات والقيود عليها، مثل $ (صواب أو خطأ أو حقيقي) $ ، لذلك ستكون clauese راضية إذا تم تعيين المتغير الأول إلى True أو المتغير الثاني إلى False أو المتغير الثالث إلى True. $ K $ يمكن أن تحتوي klauses على جميع المجموعات الممكنة من ثلاثة من $ n $ المتغيرات وعليك حدد القيمة التي يجب ضبطها لكل متغير، بحيث تكون جميع البنود راضية.

href="https://i.stack.imgur.com/hixdd.png" rel="nofollow noreferrer">

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