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 even and a function, 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 for any . 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.
Read more about Collision Problem: Classical Solution
Famous quotes containing the words collision and/or problem:
“When the wind carries a cry which is meaningful to human ears, it is simpler to believe the wind shares with us some part of the emotion of Being than that the mysteries of a hurricane’s rising murmur reduce to no more than the random collision of insensate molecules.”
—Norman Mailer (b. 1923)
“The problem of induction is not a problem of demonstration but a problem of defining the difference between valid and invalid
predictions.”
—Nelson Goodman (1906)