مشكلة الاصطدام

تعد مشكلة الاصطدام r-إلى-1 مشكلة نظرية مهمة في نظرية التعقيد والحوسبة الكمومية والرياضيات الحسابية. غالبًا ما تشير مشكلة التصادم إلى الإصدار 2 إلى 1: معطى ${\displaystyle n}$ زوجي والمعادلة${\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}$، وبالتالي f هي إما 1 إلى 1 أو 2 إلى 1. يُسمح لنا فقط بإجراء استعلامات حول قيمة ${\displaystyle f(i)}$ لأي ${\displaystyle i\in \{1,\ldots ,n\}}i\in \{1,\ldots ,n\}$. تسأل المشكلة بعد ذلك عن عدد هذه الاستعلامات التي نحتاج إلى إجرائها لتحديد ما إذا كانت f تساوي 1 إلى 1 أو 2 إلى 1.

حالة بياجباغ

حتمي

يتطلب حل الإصدار 2 إلى 1 لاستفسارات ${\textstyle {\frac {n}{2}}+1}$. وبشكل عام، يتطلب التمييز بين وظائف r-to-1 من وظائف 1 إلى 1 لاستفسارات ${\textstyle {\frac {n}{r}}+1}$.

هذا تطبيق مباشر لمبدأ التصنيف: إذا كانت الوظيفة هي r-to-1، ثم بعد استفسارات ${\textstyle {\frac {n}{r}}+1}$ نضمن أننا وجدنا تصادمًا. إذا كانت الوظيفة 1 إلى 1 ، فلا يوجد تضارب. هكذا، استفسارات ${\textstyle {\frac {n}{r}}+1}$ تكفي .إذا لم يحالفنا الحظ، فإن أول استفسار ${\displaystyle n/r}$ يمكن أن يعرض إجابات مميزة، لذلك استفسارات ${\textstyle {\frac {n}{r}}+1}$ ضرورية أيضًا.

عشوائ

إذا سمحنا بالعشوائية، فإن المشكلة أسهل. حسب مفارقة عيد الميلاد، إذا اخترنا استعلامات (مميزة) بشكل عشوائي، فمع الاحتمالية العالية نجد تضاربًا في أي وظيفة 2 إلى 1 ثابتة بعد استفسارات ${\displaystyle \Theta ({\sqrt {n}})}$.

الحل الكمي

تحل خوارزمية BHT ، التي تستخدم خوارزمية جروفرهذه المشكلة على النحو الأمثل من خلال تحويل استفسارات $O(n^{1/3})$ إلى f.