Let be positive naturals and . Define via exactly in case . Note, that the map is not necessarily injective.
Now assume one has access to just . How can one recover the list of all possible sequences via computational means, such that ? Theoretically one can go through (via lexical ordering) the list of all elements and compute each and check if . But this will have a long average running time.
Construct an algorithm, which satisfies and for all and . Further let be the total number of calls to the oracle during the execution of and
which is effectively the average running time. Find an algorithm, , such that is minimised for all , if this is at all possible.
There is a more relaxed version of this problem in which , and is a fixed value. This version may be more likely to have a polynomial time solution algorithm, or with an algorithm such that .
A basic flowchart of how the solution algorithm should function in practice:
An example procedure:
The problem instance generator decides values . This information is sent to the oracle who can perform function , and the values of , and are sent to the algorithm.
The algorithm decides to call f(0, 1) to which the oracle returns 1 as it knows exactly one of and is 1 and the rest are 0. Then, the algorithm calls f(0, 2) which returns 1 and f(1, 2) which returns 0. Since and match and both are different to , the algorithm can determine that or . The algorithm sends both, and they compared with the sent by the problem instance generator. Since there is a match, the algorithm has done a successful run for one combination of for values .
Credit to R Mathe for helping rewrite and improve this.