Collision problem

<p>The r-to-1 collision problem is an important theoretical problem in <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity theory</a>, <a href="/facts/Quantum_computing/nbbcgmvq">quantum computing</a>, and <a href="/facts/Computational_mathematics/JRoX1lu0">computational mathematics</a>. The collision problem most often refers to the 2-to-1 version: given 
  
    
      
        n
      
    
    {\displaystyle n}
  
 even and a function 
  
    
      
        f
        :
        
        {
        1
        ,
        …
        ,
        n
        }
        →
        {
        1
        ,
        …
        ,
        n
        }
      
    
    {\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}
  
, we are promised that f is either <a href="/facts/One-to-one_function/5ES6tqf5">1-to-1</a> or 2-to-1. We are only allowed to make queries about the value of 
  
    
      
        f
        (
        i
        )
      
    
    {\displaystyle f(i)}
  
 for any 
  
    
      
        i
        ∈
        {
        1
        ,
        …
        ,
        n
        }
      
    
    {\displaystyle i\in \{1,\ldots ,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.
</p>

Collision problem open-in-new

Collision problem