Collision problem
The r-to-1 collision problem is an important theoretical problem in complexity theory, quantum computing, and computational mathematics. The collision problem most often refers to the 2-to-1 version: given n even and a function f:{1,…,n}→{1,…,n}, we are promised that f is either 1-to-1 or 2-to-1. We are only allowed to make queries about the value of f(i) for any i∈{1,…,n}. The problem then asks how many such queries we need to make to determine with certainty whether f is 1-to-1 or 2-to-1.
Wikipedia contributors, "Collision problem", Wikipedia, revision 1351325255, retrieved 20 November 2026, source, CC BY-SA 4.0.