Collision problem

The r-to-1 collision problem is an important theoretical problem in complexity theory, quantum computing, and computational mathematics. The collision problem most often refers to the 2-to-1 version: given n even and a function f:\,\{1,\ldots,n\}\rightarrow\{1,\ldots,n\} , we are promised that f is either 1-to-1 or 2-to-1. We are only allowed to make queries about the value of f(i) for any i\in\{1,\ldots,n\} . The problem then asks how many such queries we need to make to determine with certainty whether f is 1-to-1 or 2-to-1.

The r-to-1 collision problem is an important theoretical problem in complexity theory, quantum computing, and computational mathematics. The collision problem most often refers to the 2-to-1 version: given n even and a function f:\,\{1,\ldots,n\}\rightarrow\{1,\ldots,n\} , we are promised that f is either 1-to-1 or 2-to-1. We are only allowed to make queries about the value of f(i) for any i\in\{1,\ldots,n\} . The problem then asks how many such queries we need to make to determine with certainty whether f is 1-to-1 or 2-to-1. Solving the 2-to-1 version deterministically requires \frac{n}{2}+1 queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires \frac{n}{r} + 1 queries. This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after \frac{n}{r} + 1 queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, \frac{n}{r} + 1 queries suffice. If we are unlucky, then the first n/r queries could return distinct answers, so \frac{n}{r} + 1 queries is also necessary.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1351325255 under CC BY-SA 4.0; modifications have been made.