Classical Solution
Solving the 2-to-1 version deterministically requires queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires queries.
This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, queries suffice. If we are unlucky, then the first queries could return distinct answers, so queries is also necessary.
If we allow randomness, the problem is easier. By the birthday paradox, if we choose (distinct) queries at random, then with high probability we find a collision in any fixed 2-to-1 function after queries.
Read more about this topic: Collision Problem
Famous quotes containing the words classical and/or solution:
“Compare the history of the novel to that of rock ‘n’ roll. Both started out a minority taste, became a mass taste, and then splintered into several subgenres. Both have been the typical cultural expressions of classes and epochs. Both started out aggressively fighting for their share of attention, novels attacking the drama, the tract, and the poem, rock attacking jazz and pop and rolling over classical music.”
—W. T. Lhamon, U.S. educator, critic. “Material Differences,” Deliberate Speed: The Origins of a Cultural Style in the American 1950s, Smithsonian (1990)
“Let us begin to understand the argument.
There is a solution to everything: Science.”
—Allen Tate (1899–1979)