هل يشير دوجلاس آدامز إلى "احتمال غير محدود" إلى P = NP؟

7

بعد أن استعدت للتو مشاركة P = NP ، بدأت أفكر: هل وصف دوغلاس آدمز من اكتشاف محرك الأقراص Infinite Improbability عن طريق استخدام جهاز Finet Improbability وهو وصف لمكان استخدام P = NP لحل مشكلة ما؟ هل هذا هو تفسيره للمشكلة؟

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

ولكن هذا كان يستغرق وقتًا طويلاً (لم يكن وقتًا كثيرًا كثير الحدود ، وربما كان N ^ p ، مع وجود p الاحتمال) لذا استسلم العلماء. ومع ذلك ، استخدم مكتشف IID محركًا محدود الاحتمالية لتخمين الحل لأي خوارزمية أو معادلة ، والمعايير المعنية ، بمعنى أنه حلها كمشكلة P كمشكلة NP.

لا يمكنني العثور على أي شيء على الويب يناقش هذا الأمر ، ولكن ربما فاتني شيء ما.

هل هذا (أو ما شابه) هو ما تعنيه دوغلاس آدامز بهذا الوصف؟ إن لم يكن ماذا يعني؟

    
مجموعة AncientSwordRage 26.09.2012 / 12:02

4 إجابة

7

فرز.

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

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

    
الجواب معين 26.09.2012 / 21:58
7

تجدر الإشارة إلى أن N في NP لا يمكن تطبيقه على مشكلات متعددة الحدود: إذا كانت X مجموعة معينة من المشكلات التي يمكن تحديدها في وقت محدد بتوصيف معين ( هو ، متعدد الحدود لـ P أو الأسي لـ EXP ) بواسطة حتمية آلة تورينج (DTM) ، ثم NX سيكون مجموعة من المشاكل التي يمكن أن تقررها غير حتمية آلة تورينج (NTM).

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

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

إذا كان IID مجرد نوع من مشكلة حسابية ، فمجرد أن يتم حل هذه المشكلة بمجرد أن توصل لك بعض البصيرة لبناء آلة تقوم بتنفيذ نوع من الدفع ، فإن السؤال هو ما مدى صعوبة هذه المشكلة؟ ليس لدينا أي إشارة على الإطلاق إلى أنها ستقع في صنف NP مشكلة كاملة. هناك الكثير من المشاكل PSPACE (= NPSPACE ) ، وفي الواقع حتى بعض NEXPTIME . إذا كان PSPACE السحري الخاص بك FID التكنولوجية المتقدمة لن يكون لك أي استخدام ، فسوف تنتظر طول الوقت. / P>

إذاً ، ستكون العلاقة بين أي من X و NX مثل "محرك الإرتجالات الثابت" و "محرك الإزاحة المحدودة". يبدو أن محرك الإيماءات اللانهائي يوافق إلى جهاز يقرر كل مشكلة في ثابتة ، بغض النظر عن مدى تعقيدها على DTM أو NTM لأنه غير محتمل إلى حد بعيد الحدث هو الأساس الذي يحدث أبدًا . لا توجد مثل هذه الأحداث يمكن التفكير فيها: حتى أن رأسين حربيين نوويين يتحولان تلقائياً إلى زبدية من زهور البتونيا ، ولا يبدو حوت العنبر المنظر مفاجئاً حلاً مستحيلاً. من المستبعد أن لا يزعج أحد أن يضع ملصقًا تحذيريًا على مثل هذه الرؤوس الحربية.

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

    
الجواب معين 27.09.2012 / 02:27
3

أعتقد أنه بإمكان استخدام محرك أقراص غير مناسب لانهائي كجزء من برنامج NP solver الذي من شأنه أن يجعل P = NP.

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

تم.

الجزء الصعب هو الحصول على محرك أقراص متواصل غير محدود.

    
الجواب معين 26.09.2012 / 18:22
2

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

هناك آثار في العالم الحقيقي إذا حدث P لتساوي NP (والقليل أننا لا نعيش بالفعل إذا لم يحدث ذلك). على سبيل المثال ، إحدى هذه المشاكل هي "إعطاء مسار التسليم إلى هذه المواقع الـ100 ، وهو الطريق الأكثر كفاءة لاتخاذ". إذا تمكنت من حل ذلك في بعض الوقت المعقول ، فستستخدم شركة التوصيل (ربما) وقودًا بنسبة 5٪ أقل في السنة. في المقابل ، تخفيض 5 ٪ من بعض أساطيل النقل الكبيرة ، وربما نرى 1.50 دولار / غالون البنزين مرة أخرى في الولايات المتحدة. وهناك العديد من هذه المشاكل. رسومات الحاسوب ، محاكاة الأرصاد الجوية ، الكثير منها. يحتوي P = NP على العديد من آثار الخيال العلمي في الواقع (بمعظم التعامل مع الكفاءات).

ولكن السفر الفوري إلى مواقع بعيدة ليس واحدًا منها.

    
الجواب معين 26.09.2012 / 14:41