مشكلة الاصطدام
المحتويات
على سبيل التعريف، تعد مشكلة الاصطدام r-إلى-1 مشكلة نظرية مهمة في نظرية التعقيد والحوسبة الكمومية والرياضيات الحسابية. غالبًا ما تشير مشكلة التصادم إلى الإصدار 2 إلى 1: معطى زوجي والمعادلة، وبالتالي f هي إما 1 إلى 1 أو 2 إلى 1. يُسمح لنا فقط بإجراء استعلامات حول قيمة لأي . تسأل المشكلة فيما بعد عن عدد هذه الاستعلامات التي نحتاج إلى إجرائها لتحديد ما إذا كانت f تساوي 1 إلى 1 أو 2 إلى 1. ونتناول فيما يلي مزيدًا من التفاصيل.
حالة بياجباغ
الحل الكمي
وعلى صعيد آخر، تحل خوارزمية BHT ، التي تستعمل خوارزمية جروفرهذه المشكلة على النحو الأمثل من خلال تحويل استفسارات إلى f.
حتمي
وفي هذا الصدد، يتطلب حل الإصدار 2 إلى 1 لاستفسارات . وبشكل عام، يتطلب التمييز بين وظائف r-to-1 من وظائف 1 إلى 1 لاستفسارات .
كذلك، هذا تطبيق مباشر لمبدأ التصنيف: إذا كانت الوظيفة هي r-to-1، ثم بعد استفسارات نضمن أننا وجدنا تصادمًا. إذا كانت الوظيفة 1 إلى 1 ، فلا يوجد تضارب. هكذا، استفسارات تكفي .إذا لم يحالفنا الحظ، فإن أول استفسار يمكن أن يعرض إجابات مميزة، لذلك استفسارات ضرورية كذلك.
عشوائ
من جانب آخر، إذا سمحنا بالعشوائية، فإن المشكلة أسهل. حسب مفارقة عيد الميلاد، إذا اخترنا استعلامات (مميزة) بشكل عشوائي، فمع الاحتمالية العالية نجد تضاربًا في أي وظيفة 2 إلى 1 ثابتة بعد استفسارات .
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟