Problema de colisión

Resolver la versión 2 a 1 de forma determinista requiere${\textstyle {\frac {n}{2}}+1}$consultas y, en general, distinguir las funciones r-a-1 de las funciones 1-a-1 requiere${\textstyle {\frac {n}{r}}+1}$consultas.

Esta es una aplicación directa del principio del palomar : si una función es r-a-1, entonces después${\textstyle {\frac {n}{r}}+1}$En las consultas, tenemos la garantía de haber encontrado una colisión. Si una función es uno a uno, entonces no existe ninguna colisión. Por lo tanto,${\textstyle {\frac {n}{r}}+1}$Las consultas son suficientes. Si tenemos mala suerte, entonces la primera${\displaystyle n/r}$Las consultas podrían devolver respuestas distintas, por lo que${\textstyle {\frac {n}{r}}+1}$Las consultas también son necesarias.

Si permitimos la aleatoriedad, el problema es más fácil. Por la paradoja del cumpleaños , si elegimos consultas (distintas) al azar, entonces con alta probabilidad encontraremos una colisión en cualquier función fija de 2 a 1 después de${\displaystyle \Theta ({\sqrt {n}})}$consultas.