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

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

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