Проблема столкновения

Не путать с проблемой обнаружения столкновений .

Проблема столкновения r-к-1 является важной теоретической проблемой в теории сложности , квантовых вычислениях и вычислительной математике . Проблема коллизий чаще всего относится к версии 2-к-1: данный $n$ даже и функция $f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}$, нам обещают, что f равно либо 1 к 1 , либо 2 к 1. Нам разрешено задавать вопросы только о значении $f(i)$ для любого $i\in \{1,\ldots ,n\}$. Затем задача состоит в том, сколько таких запросов нам нужно сделать, чтобы с уверенностью определить, является ли f отношением 1 к 1 или 2 к 1.

Классические решения

Детерминированный

Решение версии 2 к 1 детерминистически требует ${\textstyle {\frac {n}{2}}+1}$ запросы, и в целом различение функций r-к-1 от функций 1-к-1 требует ${\textstyle {\frac {n}{r}}+1}$ запросы.

Это прямое применение принципа «ячейки» : если функция имеет отношение r к 1, то после ${\textstyle {\frac {n}{r}}+1}$ запросов мы гарантированно нашли коллизию. Если функция имеет отношение 1 к 1, коллизий не существует. Таким образом, ${\textstyle {\frac {n}{r}}+1}$ запросов достаточно. Если нам не повезет, то первый $n/r$ запросы могут возвращать разные ответы, поэтому ${\textstyle {\frac {n}{r}}+1}$ запросы также необходимы.

Рандомизированный

Если мы допустим случайность, проблема станет проще. По парадоксу дня рождения , если мы выбираем (различные) запросы случайным образом, то с высокой вероятностью мы обнаружим коллизию в любой фиксированной функции 2-к-1 после $\Theta ({\sqrt {n}})$ запросы.

Квантовое решение

Алгоритм BHT , использующий алгоритм Гровера , оптимально решает эту проблему, всего лишь делая $O(n^{1/3})$ запросы к f .