ما هو "P=NP؟"، ولماذا هو سؤال مشهور؟[مغلق]

Question

ربما يكون السؤال حول ما إذا كان P=NP هو الأكثر شهرة في علوم الكمبيوتر.ماذا يعني ذلك؟ولماذا هو مثير للاهتمام؟

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

Answer 1

P لتقف على وقت متعدد الحدود.NP لتقف علي وقت كثير الحدود غير الحتمي.

تعريفات:

• وقت البولينمال يعني أن تعقيد الخوارزمية هو O(n^k)، حيث n هو حجم بياناتك (e.ز.عدد العناصر في القائمة التي سيتم فرزها)، و k هو ثابت.

• تعقيد هو الوقت الذي يقاس بعدد العمليات التي ستستغرقها، كدالة لعدد عناصر البيانات.

• عملية هو كل ما هو منطقي كعملية أساسية لمهمة معينة.لفرز العملية الأساسية هي المقارنة.بالنسبة لضرب المصفوفات، العملية الأساسية هي ضرب رقمين.

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

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

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

تعني مشكلة NP-Complete مشكلة NP X، بحيث يمكن اختزال أي مشكلة NP Y إلى X عن طريق اختزال كثير الحدود.وهذا يعني أنه إذا توصل أي شخص إلى حل متعدد الحدود لمشكلة NP كاملة، فإن ذلك سيعطي أيضًا حل متعدد الحدود لأي مشكلة NP.وهذا من شأنه أن يثبت أن P = NP.على العكس من ذلك، إذا أثبت أي شخص أن P!=NP، فسنكون على يقين من أنه لا توجد طريقة لحل مشكلة NP في زمن متعدد الحدود على جهاز كمبيوتر تقليدي.

مثال على مشكلة NP-Complete هو مشكلة العثور على تعيين الحقيقة الذي من شأنه أن يجعل التعبير المنطقي الذي يحتوي على متغيرات n صحيحًا.
في الوقت الحالي، من الناحية العملية، فإن أي مشكلة تستغرق وقتًا متعدد الحدود على TM غير حتمية لا يمكن حلها إلا في وقت أسي على TM حتمية أو على جهاز كمبيوتر تقليدي.
على سبيل المثال، الطريقة الوحيدة لحل مشكلة تعيين الحقيقة هي تجربة احتمالات 2^n.

Answer 2

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

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

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

هناك عدد كبير من المشاكل المهمة المعروفة NP-كامل (في الأساس، إذا ثبت وجود هذه المشاكل ص, ، ثم الجميع NP ثبت أن المشاكل موجودة ص).لو ص = NP, ، فسيتم إثبات أن كل هذه المشكلات لها حل فعال (زمن متعدد الحدود).

ويعتقد معظم العلماء ذلك ص!=NP.ومع ذلك، لم يتم حتى الآن إثبات أي منهما ص = NP أو ص!=NP.فمن قدم دليلاً على أي من التخمينين، سيفوزون بمليون دولار أمريكي.

Answer 3

لإعطاء أبسط إجابة يمكنني التفكير فيها:

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

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

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

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

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

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

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

Answer 4

مختصر من معرفتي المتواضعة:

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

مشاكل أخرى، مثل العثور على مسار يعبر كل قمة في الرسم البياني أو الحصول على مفتاح RSA الخاص من المفتاح العام يكون أكثر صعوبة (O(e^n)).

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

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

وهي مشكلة ملهمة جدًا.

Answer 5

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

Answer 6

أولاً: بعض التعريفات:

• توجد مشكلة معينة في P إذا كان بإمكانك حساب الحل في وقت أقل من n^k بالنسبة للبعض k, ، أين n هو حجم الإدخال.على سبيل المثال، يمكن إجراء الفرز في n log n وهو أقل من n^2, ، لذا فإن الفرز هو وقت كثير الحدود.

• هناك مشكلة في NP إذا كان هناك ملف k بحيث يوجد حل للحجم على الأكثر n^k والتي يمكنك التحقق منها في الوقت المناسب على الأكثر n^k.خذ 3-تلوين الرسوم البيانية:في ضوء الرسم البياني، فإن التلوين 3 عبارة عن قائمة من الأزواج (الرأس، اللون) التي لها حجم O(n) ويمكنك التحقق في الوقت المناسب O(m) (أو O(n^2)) ما إذا كان جميع الجيران لديهم ألوان مختلفة.لذا فإن الرسم البياني يكون قابلاً للتلوين بثلاثة ألوان فقط إذا كان هناك حل قصير ويمكن التحقق منه بسهولة.

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

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

لماذا السؤال P =? NP مثير للاهتمام؟للإجابة على ذلك، يحتاج المرء أولاً إلى معرفة ما هي المسائل NP-Complete.ببساطة،

• تكون المشكلة L مكتملة بـ NP إذا كان (1) L موجودًا في P، و(2) يمكن استخدام خوارزمية تحل L لحل أي مشكلة L' في NP؛أي أنه في ضوء مثيل L'، يمكنك إنشاء مثيل L له حل إذا وفقط إذا كان مثيل L' يحتوي على حل.من الناحية الرسمية، كل مشكلة L' في NP موجودة قابل للاختزال إلى ل.

لاحظ أن مثيل L يجب أن يكون قابلاً للحساب في زمن متعدد الحدود وله حجم متعدد الحدود بحجم L'؛بهذه الطريقة، فإن حل مسألة NP-Complete في زمن متعدد الحدود يمنحنا حلًا زمنيًا متعدد الحدود الجميع مشاكل NP.

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

لكل قمة v، يوجد متغيرين منطقيين v_h وv_l، والمتطلبات (v_h أو v_l):يمكن أن يحتوي كل زوج على القيم {01، 10، 11} فقط، والتي يمكننا اعتبارها اللون 1 و2 و3.

لكل حافة (u، v)، يجب أن يكون (u_h، u_l) != (v_h، v_l).إنه،

not ((u_h and not u_l) and (v_h and not v_l) or ...)تعداد جميع التكوينات المتساوية والاشتراط على عدم وجود أي منها.

AND'جمع كل هذه القيود معًا يعطي صيغة منطقية ذات حجم متعدد الحدود (O(n+m)).يمكنك التحقق من أن الأمر يستغرق وقتًا متعدد الحدود لحسابه أيضًا:أنت تقوم بعمل واضح O(1) الأشياء لكل قمة ولكل حافة.

إذا تمكنت من حل الصيغة المنطقية التي قمت بإنشائها، فيمكنك أيضًا حل تلوين الرسم البياني:لكل زوج من المتغيرات v_h وv_l، اجعل لون v هو اللون المطابق لقيم تلك المتغيرات.من خلال بناء الصيغة، لن يكون لدى الجيران ألوان متساوية.

ومن ثم، إذا كان التلوين ثلاثي الرسوم البيانية مكتملًا بـ NP، فإن ذلك يكون أيضًا استيفاء الصيغة المنطقية.

نحن نعلم أن التلوين الثلاثي للرسوم البيانية هو NP كامل؛ومع ذلك، فقد عرفنا ذلك تاريخيًا من خلال إظهار اكتمال NP لأول مرة لإرضاء الدائرة المنطقية، ثم تقليل ذلك إلى 3 قابلية للتلوين (بدلاً من العكس).