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

formula_1 زوجي والمعادلةformula_2، وبالتالي f هي إما 1 إلى 1 أو 2 إلى 1. يُسمح
ما هو تحديد مشكلة التصادم 2 إلى 1 وكيف يتعلق ذلك بالمعادلات formula_1 و formula_2؟

حالة بياجباغ. حتمي يتطلب حل الإصدار 2 إلى 1 
كيف يمكننا استعمال استعلامات حول قيمة formula_3 لتحديد ما إذا كانت الوظيفة f تساوي 1 إلى 1 أم 2 إلى 1؟

يمكن أن يعرض إجابات مميزة
كيف يمكن التمييز بين وظائف r-to-1 ووظائف 1 إلى 1 في استفسارات formula_6؟
