I was looking at this question. So if I understand the above discussion right th

Question

I was looking at this question.

So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then one can't using this uniformly at random sample a permutation of another finite set (chosen may be adversarially) and also have the algorithm be guaranteed to halt.

Is the above summary right? Is there a reference to a proof of the above?

Is there a fundamental understanding of this impossibility?

If one is allowed say (1) exponential space or (2) the oracle was picking the numbers with some bias then can we get across this impossibility?

What are the consequences if hypothetically one could do the above?

Explanation / Answer

No, the summary is not correct. Your "if...then...." statement cannot possibly be correct, as we do know ways to sample a permutation of a finite set uniformly at random (under reasonable assumptions). For instance, one method is to repeatedly (n times) sample without replacement. What that question is saying is that there is no number t such that we can say with sure that the algorithm will terminate after at most t steps; there will always be some tiny chance it takes longer than t steps. However, the probability it will take longer than cn2 steps (say) is exponentially small in c, so this is basically just a theoretical quibble -- for all practical purposes, the running time is O(n2)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.