اشرح الدليل من قبل Vinay Deolalikar أن P! = NP [مغلق
https://stackoverflow.com/questions/3436978
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianالمحلول
لقد قمت فقط بمسح الورقة ، ولكن إليك ملخصًا تقريبيًا لكيفية معلق كل شيء معًا.
من الصفحة 86 من الورقة.
... تنجح خوارزميات الزمن متعدد الحدود من خلال "تقسيم" المشكلة على التوالي إلى مشكلات فرعية أصغر تنضم إلى بعضها البعض من خلال الاستقلال المشروط. وبالتالي ، لا يمكن لخوارزميات الزمن متعدد الحدود حل المشكلات في الأنظمة التي تتطلب فيها كتلها من أجل الحصول على حل المشكلة الدقة المتزامنة.
تُظهر أجزاء أخرى من الورقة أنه لا يمكن تفكيك بعض مشاكل NP بهذه الطريقة. وبالتالي NP/= P
يتم إنفاق الكثير من الورقة في تحديد الاستقلال المشروط وإثبات هاتين النقطتين.
نصائح أخرى
ديك ليبتون لديه لطيف إدخال المدونة حول الورقة وانطباعاته الأولى. لسوء الحظ ، فهي تقنية أيضا. من ما يمكنني فهمه ، يبدو أن الابتكار الرئيسي لـ Deolalikar هو استخدام بعض المفاهيم من الفيزياء الإحصائية ونظرية النموذج المحدود وربطها بالمشكلة.
أنا مع Rex M مع هذا ، بعض النتائج ، ومعظمها لا يمكن التعبير عن النتائج الرياضية للأشخاص الذين يفتقرون إلى الإتقان التقني.
أعجبني هذا ( http://www.newscientist.com/article/dn19287-p-np-its-bad-news-for-the-power-of-computing.html ):
تدور حجته حول مهمة معينة ، وهي مشكلة الرضا المنطقية ، والتي تسأل ما إذا كان يمكن أن تكون مجموعة من البيانات المنطقية صحيحة في وقت واحد أو ما إذا كانت تتناقض مع بعضها البعض. من المعروف أن هذه مشكلة NP.
يدعي Deolalikar أنه أظهر أنه لا يوجد برنامج يمكنه إكماله بسرعة من نقطة الصفر ، وبالتالي فهو ليس مشكلة P. تتضمن حجته الاستخدام العبقري للفيزياء الإحصائية ، لأنه يستخدم بنية رياضية تتبع العديد من القواعد نفسها مثل النظام المادي العشوائي.
يمكن أن تكون آثار ما سبق مهمة للغاية:
إذا كانت النتيجة قائما ، فستثبت أن الفئتين P و NP غير متطابقين ، وفرض حدود شديدة على ما يمكن أن تنجزه أجهزة الكمبيوتر - مما يعني أن العديد من المهام قد تكون معقدة بشكل أساسي.
بالنسبة لبعض المشكلات - بما في ذلك العوامل - فإن النتيجة لا تقول بوضوح ما إذا كان يمكن حلها بسرعة. ولكن سيتم محكوم على مجموعة فرعية ضخمة من المشكلات التي تسمى "NP-Complete". ومن الأمثلة الشهيرة مشكلة بائع السفر - العثور على أقصر طريق بين مجموعة من المدن. يمكن فحص مثل هذه المشكلات بسرعة ، ولكن إذا كان P ≠ NP ، فلا يوجد برنامج كمبيوتر يمكنه إكمالها بسرعة من نقطة الصفر.
هذا هو فهمي لتقنية الإثبات: إنه يستخدم منطقًا من الدرجة الأولى لتوصيف جميع خوارزميات الوقت متعدد الحدود ، ثم يوضح أنه بالنسبة لمشاكل SAT الكبيرة مع بعض الخصائص التي لا يمكن أن تحدد خوارزمية زمنية متعددة الحدود رضائها.
إحدى الطرق الأخرى للتفكير في الأمر ، والتي قد تكون خاطئة تمامًا ، ولكنها أول انطباع عني لأنني أقرأها في الممر الأول ، هي أننا نفكر في تعيين/تطهير المصطلحات في رضا الدائرة على أنها تشكيل وكسر مجموعات "مطلوبة" بنية '، وأنه يستخدم فيزياء إحصائية لإظهار أنه لا توجد سرعة كافية في العمليات متعددة الحدود لأداء تلك العمليات في "مساحة مرحلة" معينة من العمليات ، لأن هذه "المجموعات" تنتهي ببعضها البعض.
هذا الدليل يجب أن يغطي جميع فئات الخوارزميات ، مثل التحسين العالمي المستمر.
على سبيل المثال ، في مشكلة 3 سات يتعين علينا تقييم المتغيرات لتحقيق جميع بدائل ثلاثية من هذه المتغيرات أو نفيها. انظر الى x OR y يمكن تغييرها إلى تحسين
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
وسبعة مصطلحات مماثلة لبديل ثلاثة متغيرات.
إن العثور على الحد الأدنى العالمي لمجموع كثير الحدود لجميع المصطلحات من شأنه أن يحل مشكلتنا. ((مصدر)
إنها تخرج من تقنيات التوافقي القياسية إلى العالم المستمر باستخدام أساليب _gradient ، والأقلام المحلية لإزالة الأساليب ، والخوارزميات التطورية. إنها مملكة مختلفة تمامًا - التحليل العددي - لا أعتقد أن مثل هذا الدليل يمكن أن يغطي حقًا (؟)
تجدر الإشارة إلى أنه مع البراهين ، "الشيطان في التفاصيل". من الواضح أن النظرة العامة ذات المستوى العالي هي شيء مثل:
بعض العلاقة بين العناصر ، تبين أن هذه العلاقة تعني x وهذا يعني y وبالتالي يتم عرض حجتي.
أعني ، قد يكون ذلك عبر تعريفي أو أي شكل آخر من أشكال إثبات الأشياء ، لكن ما أقوله هو نظرة عامة على المستوى العالي لا طائل منه. لا فائدة من شرح ذلك. على الرغم من أن السؤال نفسه يتعلق بعلوم الكمبيوتر ، إلا أنه من الأفضل ترك علماء الرياضيات (يعتقد أنه بالتأكيد مثير للاهتمام بشكل لا يصدق).
