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

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

حالة بياجباغ

حتمي

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

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

عشوائ

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

الحل الكمي

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