Kollisionsproblem

r -till-1-kollisionsproblemet är ett viktigt teoretiskt problem inom komplexitetsteori , kvantberäkning och beräkningsmatematik . Kollisionsproblemet hänvisar oftast till 2-till-1-versionen: given $n$ jämn och en funktion ${\displaystyle f:\, \{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}} ,$ vi lovas att f är antingen 1-till-1 eller 2-till-1. Vi får endast göra frågor om värdet av $f(i)$ för alla $i\in \{1,\ldots ,n\}$ . Problemet frågar sedan hur många sådana frågor vi behöver göra för att med säkerhet avgöra om f är 1-till-1 eller 2-till-1.

Klassiska lösningar

Deterministisk

För att lösa 2-till-1-versionen deterministiskt krävs ${\textstyle {\frac {n}{2}}+1}$ -frågor, och generellt krävs det att särskilja r-till-1-funktioner från 1-till-1-funktioner ${\textstyle {\frac {n}{r}}+1}$ frågor.

Detta är en enkel tillämpning av duvhålsprincipen : om en funktion är r-till-1, så efter ${\textstyle {\frac {n}{r}}+1}$ -frågor har vi garanterat hittat en kollision. Om en funktion är 1-till-1, existerar ingen kollision. Således ${\textstyle {\frac {n}{r}}+1}$ frågor. Om vi ​​har otur kan de första $n/r$ frågorna returnera distinkta svar, så ${\textstyle {\frac {n}{r}}+1}$ frågor är också nödvändiga.

Randomiserad

Om vi ​​tillåter slumpmässighet är problemet lättare. Enligt födelsedagsparadoxen , om vi väljer (distinkta) frågor slumpmässigt, så hittar vi med hög sannolikhet en kollision i vilken fast 2-till-1-funktion som helst efter $\Theta ({\sqrt {n}} )$ frågor.

Kvantlösning

BHT -algoritmen , som använder Grovers algoritm , löser detta problem optimalt genom att endast göra ${\displaystyle O(n^{1/3})}-$ frågor till f .