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

تعد مشكلة الاصطدام r-إلى-1 مشكلة نظرية مهمة في نظرية التعقيد والحوسبة الكمومية والرياضيات الحسابية. غالبًا ما تشير مشكلة التصادم إلى الإصدار 2 إلى 1: معطى











n









{\displaystyle {\displaystyle n}}



زوجي والمعادلة











f

:



{

1

,

…

,

n

}

→

{

1

,

…

,

n

}





f

:



{

1

,

…

,

n

}

→

{

1

,

…

,

n

}





{\displaystyle {\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}



، وبالتالي f هي إما 1 إلى 1 أو 2 إلى 1. يُسمح لنا فقط بإجراء استعلامات حول قيمة











f

(

i

)









{\displaystyle {\displaystyle f(i)}}



لأي











i

∈

{

1

,

…

,

n

}





i

∈

{

1

,

…

,

n

}





{\displaystyle {\displaystyle i\in \{1,\ldots ,n\}}i\in \{1,\ldots ,n\}}



. تسأل المشكلة بعد ذلك عن عدد هذه الاستعلامات التي نحتاج إلى إجرائها لتحديد ما إذا كانت f تساوي 1 إلى 1 أو 2 إلى 1.