Problema de colisión

---

El problema de colisión r-a-1 es un problema teórico importante en la teoría de la complejidad , la computación cuántica y las matemáticas computacionales . El problema de colisión con mayor frecuencia se refiere a la versión 2 a 1: ^[1] dado par y una función , se nos promete que f es 1 a 1 o 2 a 1. Solo podemos realizar consultas sobre el valor de for any . Entonces, el problema pregunta cuántas consultas de este tipo debemos realizar para determinar con certeza si f es 1 a 1 o 2 a 1.${\ Displaystyle n}$${\ Displaystyle f: \, \ {1, \ ldots, n \} \ rightarrow \ {1, \ ldots, n \}}$${\ Displaystyle f (i)}$${\ Displaystyle i \ in \ {1, \ ldots, n \}}$

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

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

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

El algoritmo BHT , que usa el algoritmo de Grover , resuelve este problema de manera óptima solo haciendo consultas a f .${\ Displaystyle O (n ^ {1/3})}$

---