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

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

Состояние Баягбага

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

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

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

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

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

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

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

Рекомендации

1. Скотт Ааронсон (2004). «Пределы эффективных вычислений в физическом мире» (PDF ).