El problema de la 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 suele referirse 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. Sólo podemos realizar consultas sobre el valor de for any . Luego, el problema pregunta cuántas consultas de este tipo necesitamos hacer para determinar con certeza si f es 1 a 1 o 2 a 1.
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.
Esta es una aplicación sencilla del principio del casillero : si una función es r a 1, luego de las consultas tenemos la garantía de haber encontrado una colisión. Si una función es 1 a 1, entonces no existe ninguna colisión. Por tanto, las consultas son suficientes. Si no tenemos suerte, las primeras consultas podrían arrojar respuestas distintas, por lo que las consultas también son necesarias.
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.
El algoritmo BHT , que utiliza el algoritmo de Grover , resuelve este problema de manera óptima al realizar únicamente consultas a f .
