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

Question

قل لدي مجموعتين من القيم $ $ و $ B $ ولكل مجموعة لديك وظيفة حسابية من تلك المجموعة إلى مجموعة ثالثة $ C $ . افترض الآن أنني أريد إنشاء وظيفة من $ $ إلى $ B $ ، بحيث إذا كنت إنشاء هذه الوظيفة مع $ B $ إلى $ C $ الوظيفة المذكورة أعلاه أحصل على وظيفة تنتج نفس النتائج مثل $ $ إلى $ C $ الوظيفة المذكورة أعلاه.

إذا كنت أعرف الوقت التعقيد للوظائفتين التي تعيد عناصر $ c $ ، هل هذا يسمح لي أن أقول أي شيء عن وظيفة من $ $ إلى $ B $ مع الخاصية المحددة؟ على سبيل المثال، يمكن وضع أي حدود على التعقيد الحسابي لهذه الوظيفة؟ هل يمكن أن نقول حتى ما إذا كانت هذه الوظيفة محسمة أم لا؟

Answer 1

يمكننا أن يكون لدينا مجموعات $ a، b، c $ مع خرائط قياسية خطية $ f: a \ to C $ و $ g: b \ to c $ بحيث يوجد خريطة $ h: a \ إلى B $ مع $ f= g \ circ h h $ ، ولكن تعقيد الوقت اللازم / تورينج درجة ل $ H $ هو عالية كما تريد.

دليل على: اختيار خريطة $ h: \ sigma ^ * \ to \ sigma ^ * $ وهو أمر صعب في أي معنى كنت مخفض. الآن دع $ a= c=sigma ^ * $ ، و $ b={\ langle w، h (w ) \ التغذية \ منتصف W \ في \ سيغما ^ * \} $ . دع $ f=mathrm {ID} $ و $ g=pi_1 $ ، أي $ g (\ langle w، u \ rangle)= w دولار . الآن $ a، b، c $ $ f، g $ تلبية معايير المطالبة، و الخريطة الوحيدة $ h $ تعمل $ h (w)=lange w، h (w) \ rangle $ ، وهو أمر صعب للغاية مثل $ H $ .

Answer 2

أنت تطلب سؤالين، أحدهما حول الحساب وواحد حول التعقيد الحسابي.الحكم المعتاد هو طرح سؤال واحد لكل وظيفة.سأجيب على السؤال الثاني.لا، بموجب التخمين القياسي، يمكن أن يكون التعقيد الحسابي سيئا للغاية.افترض $ f: a \ t $ "span class=" حاوية الرياضيات "> $ f (x)=alpha ^ x \ bmod P $ و $ g: b \ to c $ يتم إعطاء بواسطة $ g (x)=beta ^ x\ BMOD P $ ، حيث $ P $ هو رقم رئيسي كبير.ثم يمكنك حساب $ f، g $ في وقت متعدد الحدود؛ولكن العثور على خريطة $ a \ t $ هو أمر صعب مثل الحوسبة السجل المنفصل من $ \ beta $ إلى قاعدة $ \ ألفا $ ، والذي تم تخمينه ليكون صعبا.

Answer 3

تشفير المفتاح العام يعتمد على فكرة أن التعقيد يمكن أن يكون مرتفعا للغاية.

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