ما هو مفقود لهذا P! = برهان NP؟

Question

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

الآن سؤالي هو: لا يؤدي هذا إلى أن P! = NP منذ "استرداد كلمة المرور" هو عنصر من NP يمكن عرضه يتطلب أكثر من وقت متعدد الحدود لتشغيله؟

Answer 1

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

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

Answer 2

إذا أظهرت ذلك أي الخوارزمية التي تحل "استعادة كلمة المرور" تتطلب أكثر من وقت متعدد الحدود، ثم توضح أن P ≠ NP.

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

Answer 3

NP لا يعني "nonpolynomial"، إذا كان هذا ما كنت تفكر فيه (واعتذاري مقدما إذا لم تكن كذلك!). وهذا يعني "كثير الحدود غير المرن". خوارزمية Nondeterministic هي واحدة تعادل عدد غير محدود من المثيلات الموازية للخوارزمية. كمثال على سبيل المثال، العثور على كلمة المرور الصحيحة بالقوة الغاشمة هو متعدد الحدود غير المرن: إذا كنت تتخيل أن التحقق من كلمة المرور، إذا حدث تخميرك صحيحا، فاخذ وقتا خطيا (أي متعدد الحدود) على طول كلمة المرور، ولكن تحتاج إلى ذلك تحقق من عدد التعسفي من كلمات المرور المحتملة (k ^ n) بالتوازي، ثم تكلفة العثور على الحل باستخدام هذه الطريقة هي متعدد الحدود غير المرمونة.

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

Answer 4

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

الآن، إليك طريقة واحدة يمكنك القيام بها في تحويل هذا إلى دليل على أن P! = NP:

1) إظهار أن "استعادة كلمة المرور" هي NP-Complete. وهذا هو، أي مشكلة في NP يمكن تخفيضها إلى "استعادة كلمة المرور" في وقت متعدد الحدود. (أي أن هناك خوارزمية فعالة لتحويل أي مشكلة NP أخرى إلى "استرداد كلمة المرور".)

2) بمجرد أن يكون ذلك بعد ذلك، بينما يذكر بافل، فإنه لا يكفي لإظهار أن الخوارزمية البديهية غير متعددة الحدود. يجب عليك إظهار أنه لا توجد خوارزمية متعددة الحدود لحل "استرداد كلمة المرور". مهمة صعبة للغاية.

(*) Edmund هو أيضا على حق: NP يعني متعدد الحدود على جهاز غير محدد. التحقق متعدد الحدود هو في الأساس المسار الذي تم اختياره بواسطة الجهاز غير المحدد.

Answer 5

1. كما هو مذكور، "استرداد كلمة المرور" ليست مشكلة في القرار.
2. لم تثبت أن "استرداد كلمة المرور" لا يحتوي على خوارزمية زمنية متعددة الحدود، لقد جادلت فقط بأسباب بديهية لا. فقط لأن مساحة الحل هي عملاقة لا تعني أنه لا توجد خوارزميات سريعة للعثور على الحل؛ على سبيل المثال، هناك n! التباديل من مجموعة من n أعداد صحيحة مميزة ولكن يتم فرز واحد فقط تصاعدي حتى الآن يمكننا العثور عليه في n log n الوقت. مثال أكثر متعة، انظر مشروع Euler # 67.
3. حتى إذا قمت بإعادة صياغة "استرداد كلمة المرور" كأداة قرار وتمكنت من إظهار أن هناك خوارزمية زمنية متعددة الحدود لحلها، عليك الآن إثبات أن "استعادة كلمة المرور" هي NP-Complete.

للحصول على تفاصيل حول P / NP / ETC. انظر الى هذا السؤال السابق.

Answer 6

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

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

وهذا يعني: أنت (بعض المستجيبين الآخرين) لديهم يفترض أن كلمة المرور Munging Routine تحتوي على جميع الخصائص التي أراد المصممون بها. هذا سيكون ليكون اثبت.

Answer 7

كتابة هذه الإجابة لأنني أتيحت لي هذه الفكرة في مرحلة ما، وكانت الإجابات هنا غير مرضية.

لقد أثبتت أن P = / = NP تحت وجود "Oracle" (هذا هو الشيء الذي يخبر ما إذا كانت كلمة المرور صحيحة أم لا).

لقد ثبت أنك لا تستطيع أنه لا تثبت أن NP الأصلي P VS باستخدام Oracles (تسمى هذه التقنية الاستئناف).

من أجل إثبات المشكلة الأصلية، عليك تحديد Oracle من حيث آلة Turing. بمعنى آخر، عليك أن تصف خدمة كلمة المرور مع الإدخال، ثم أثبت أنه لا توجد خوارزمية يمكنها تخمين كلمة المرور معينة رمز التحقق من كلمة المرور.

لاحظ أنه عليك القيام بذلك لأي التحقق من كلمة مرور سريعة ممكنة. الشرط الوحيد لخوارزمية التحقق من كلمة المرور هي أنه يعمل في وقت بولينيا فيما يتعلق بطول كلمة المرور.

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