Problém s kolizí - Collision problem

The Problém kolize r-to-1 je důležitý teoretický problém v teorie složitosti, kvantové výpočty, a výpočetní matematika. Problém s kolizí se nejčastěji týká verze 2 na 1:^[1] daný ${displaystyle n}$ sudá a funkce ${displaystyle f:, {1, ldots, n} ightarrow {1, ldots, n}}$, je nám slíbeno, že f je buď 1: 1 nebo 2: 1. Jsme oprávněni činit dotazy pouze na hodnotu ${displaystyle f (i)}$ pro všechny ${displaystyle iin {1, ldots, n}}$. Problém se poté zeptá, kolik takových dotazů musíme udělat, abychom mohli s jistotou určit, zda f je 1: 1 nebo 2: 1.

Stav Bayagbag

Deterministický

Řešení verze 2 na 1 deterministicky vyžaduje ${extstyle {frac {n} {2}} + 1}$ obecně vyžaduje rozlišování funkcí r-to-1 od funkcí 1: 1 ${extstyle {frac {n} {r}} + 1}$ dotazy.

Jedná se o přímou aplikaci princip pigeonhole: pokud je funkce r-to-1, pak po ${extstyle {frac {n} {r}} + 1}$ zaručeně jsme našli kolizi. Pokud je funkce 1: 1, pak žádná kolize neexistuje. Tím pádem, ${extstyle {frac {n} {r}} + 1}$ dotazy stačí. Pokud máme smůlu, pak první ${displaystyle n / r}$ dotazy by mohly vrátit odlišné odpovědi, takže ${extstyle {frac {n} {r}} + 1}$ dotazy jsou také nezbytné.

Náhodně

Pokud povolíme náhodnost, problém je jednodušší. Podle narozeninový paradox, pokud náhodně vybereme (odlišné) dotazy, pak s vysokou pravděpodobností najdeme kolizi v jakékoli pevné funkci 2 na 1 po ${displaystyle Theta ({sqrt {n}})}$ dotazy.

Kvantové řešení

The Algoritmus BHT, který používá Groverův algoritmus, řeší tento problém optimálně pouze výrobou ${displaystyle O (n ^ {1/3})}$ dotazy na F.

Reference

Tento fyzika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.