7
$\begingroup$

This question compares "strict" polynomial time, as opposed to "expected" polynomial time.

Let $S = \{1,2,…,n\}$, and let $O$ be an ordering on elements of $S$ (the number of orderings is $n!$).

A probabilistic algorithm can easily select a random ordering in "strict" polynomial time (in $1^n$), as follows:

Let O = {}, T = S
For i = 1 To n
    Let e be a random element from T
    Let T = T - {e}
    Let O = O ∪ {(i,e)}

The algorithm assumes that sampling a random element from $T$ can be performed in strict polynomial time. (More precisely, we assume that in strict polynomial time, we can uniformly sample from any set whose size is polynomial in $n$.)

Now let's consider the following problem:

Choose $m$ distinct random permutations over $S$, where $m$ = poly($n$) < $n!$.

One naive way of doing this is to repeat the above algorithm, keep a record of permutations selected thus far. If the algorithm returns a "redundant" permutation, throw it away, and start over.

The above approach works in "expected" polynomial time, rather than "strict" polynomial time.

Is there a strict polynomial time which does the job?

Edit: Here's a reference for those who want to know more on "strict vs. expected" issue: On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits.

$\endgroup$
  • 2
    $\begingroup$ Do you want to generate m distinct permutations uniformly at random or just m permutations uniformly at random? $\endgroup$ – Robin Kothari Jun 7 '11 at 12:58
  • 1
    $\begingroup$ @singhsumit: No, the resulting algorithm is still probabilistic; it just runs in strict rather than expected time. @Robin: thanks, corrected. @Tyson: I know. That's exactly why I made that assumption. That is, IF you assume sampling $T$ is possible in strict polynomial time, can we solve the rest? $\endgroup$ – Rahab Jun 7 '11 at 14:28
  • 1
    $\begingroup$ there is a standard transformation that will give you an algorithm which fails with small probability and runs always in polynomial time: run the algorithm that has expected polynomial time $T$ for $T/\delta$ steps, and if it hasn't halted yet, output fail. by markov, the fail prob. is $\delta$. $\endgroup$ – Sasho Nikolov Jun 7 '11 at 14:31
  • 1
    $\begingroup$ @Sasho: I'm afraid failure of the algorithm is not an option for me. I want it to work correctly all the time, and never run over a certain (polynomial) time. $\endgroup$ – Rahab Jun 7 '11 at 14:36
  • 1
    $\begingroup$ @Rahab: Do you need an exactly uniform distribution? If you can settle for an approximation which is $\epsilon$ close, then it seems there is an easy exact poly time algorithm, since you just repeat $k$ is you generate a redundant permutation, you just retry up to a maximum of $k$ times, and then return permutation $P$, where $P$ is the lowest non-redundant permutation according to some fixed ordering. Since $P$ is always less than $M+1$ this permutation can be found in polynomial time $\endgroup$ – Joe Fitzsimons Jun 7 '11 at 16:55
9
$\begingroup$

I believe the answer is that it is possible in polynomial time as follows:

Each permutation of $N$ can be expressed as a function $f(x)$ which maps an input index to the corresponding output index. Each such function can be expressed as a string $f(1) + f(2) + f(3) + ... + f(N)$, where $+$ is the concatentaion operator. Thus there is a natural lexicographic ordering on the permutations. The idea is to pick the permutations in lexicographic order.

The probability $p_{i,1}$ that permutation $P_i$ will be the first permutation (in lexicographic order) from a set of $M$ permutations of $N$ elements chosen uniformly at random will be $$p_{i,1} = \frac{\binom{N-i}{M-1}}{\binom{N}{M}}.$$

By making a random choice from this probability distribution we determine the first permutation in our set. Let's assume that this permutation is indexed by $x_1$. We now need to choose the permutation which is second lowest in lexicographic order. Clearly, this is the same problem as before, but now we need to choose according to the probability distribution $$p_{i,2} = \frac{\binom{N-x_1-i}{M-2}}{\binom{N-x_1}{M-1}}.$$

For an arbitrary ranking $k$ the probability distribution will be given by $$p_{i,k} = \frac{\binom{N-i-\sum_{j=1}^{k-1} x_j}{M-k}}{\binom{N-\sum_{j=1}^{k-1}x_j}{M-k+1}}.$$

This process is repeated until we have chosen all $M$ permutations. As there is no possibility of collision, the process terminates after exactly $M$ such choices, and hence is an exact polynomial time computation assuming the random choice can be made in time $\mbox{poly}(N)$.


UPDATE: Kaveh points out in the comments below that I have not shown how to find the $i$th permutation in time polynomial in $n$, so here is one way.

We can turn an permutation into an integer by taking $I_P = \sum_{k=0}^{n-1} \frac{n!}{(n-i)!} (y_k-1)$. Here $y_k$ is defined as follows: Let $S_0$ be the set of integers from 1 to $N$, and take $S_k = S_0 / \{f(x)\}_{x=1}^k$. Then $y_k$ is the lexicographic index of $f(k+1)$ in $S_k$. Note that $y_k$ is always an integer between 1 and $n-k$. Thus you obtain a unique integer between 0 and $n!-1$ for every permutation. To reverst this and find the $i$th permutation is trivial, since $y_0 = (I_P \mbox{ mod } n)+1$, $y_1 = ((I_P-y_0)/n \mbox{ mod } n)+1$ etc., and once all $y_k$ have been calculated, $f(x)$ can be calculated by taking $f(1) = y_0$, which allows you to calculate $S_1$, which in turn gives you $f(2)$, etc.

Thus you have a polynomial time algorithm for converting a permutation of $n$ items into a unique integer between $0$ and $n!-1$ and back.


This answer makes an assumption that it is possible to generate probabilities of the necessary form, which is not necessarily granted in the question. See the answer for Peter Shor for why this can be a problem.

$\endgroup$
  • 2
    $\begingroup$ Given $1 \leq i \leq n!$, can we find the $i$th permutation over $[n]$ in the lexicographic ordering in time polynomial in $n$? Probably this is trivial but I don't see it. $\endgroup$ – Kaveh Jun 8 '11 at 4:35
  • 2
    $\begingroup$ If we can enumerate the subsets of size $m$ of a set (of size $N=n!$), we can just pick a random number $0 \leq i < {N \choose m}$ and it will give the required $m$ permutations. And mapping $i$ to the corresponding $m$ permutation in time polynomial in $n$ and $m$ seems to be similar to that of computing the $i$th permutation in time polynomial in $n$. $\endgroup$ – Kaveh Jun 8 '11 at 4:39
  • 2
    $\begingroup$ @Kaveh: Good question! Yes, it is indeed possible to find the $i$th permutation in polynomial time. It is a bit long to fit in a comment so I have appended it to the answer above. As regards your second comment, $\binom{N}{m}$ is potentially huge, so you'd have to fix $m$ and choose only from these combinations, but that might well be another way to go. $\endgroup$ – Joe Fitzsimons Jun 8 '11 at 12:45
  • $\begingroup$ @Kaveh: Do you want to post your comment as an answer? If so I can remove my other answer, which is quite close to it (and extremely derivative!). $\endgroup$ – Joe Fitzsimons Jun 8 '11 at 16:19
  • $\begingroup$ @Joe, no, I don't, but thanks for asking. :) $\endgroup$ – Kaveh Jun 8 '11 at 16:21
6
$\begingroup$

If the only randomness you can obtain is sampling from a set of polynomial size, you are not going to be able to get two random permutations, because the probability of any particular pair of random permutations is $$ \frac{2}{n! (n! - 1)} $$ and $n!-1$ doesn't necessarily factor into polynomial-size numbers.

$\endgroup$
  • $\begingroup$ It seems obvious that there exist arbitrarily large $n$ for which $n!-1$ is not polynomially smooth, but do you have a proof of that? $\endgroup$ – David Eppstein Mar 22 '16 at 20:42
  • $\begingroup$ @David Eppstein: No, I don't. I can offer experimental evidence, for what it's worth: $n!-1$ is prime for 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974, 1963, 3507, 3610, 6917, 21480, 34790, 94550, 103040, 147855. $\endgroup$ – Peter Shor Mar 22 '16 at 21:47
  • $\begingroup$ Despite my previous answers, I completely agree with this. The previous answers assume make an assumption about the randomness that can be generated which may be incorrect for the setting. I guess it is implicit in the question that the only randomness comes from uniform choices from poly-sized sets. I didn't read it that way, probably in part because the example in the question seems to directly choose a permutation, but of course this could be achieved by making choices from a collection of smaller sets. In retrospect, this appears to be the correct interpretation of the question. $\endgroup$ – Joe Fitzsimons Mar 23 '16 at 3:35
  • $\begingroup$ It seems at some point my past self tried to argue that the probabilities could be chosen using uniform choices from poly sized sets in the comments of one of the answers. Clearly this was wrong. $\endgroup$ – Joe Fitzsimons Mar 23 '16 at 5:47
5
$\begingroup$

Here is a much simpler solution to the one posted in my previous answer, inspired by Kaveh's comment, which reuses the trick of changing a permutation to a unique integer and back which I quote below (in case an edit to the other answer removes or changes it). Conveniently this new approach does not require you to specify $m$ ahead of time.

We can turn a permutation into an integer by taking $I_P = \sum_{k=0}^{n-1} \frac{n!}{(n-k)!} (y_k-1)$. Here $y_k$ is defined as follows: Let $S_0$ be the set of integers from 1 to $N$, and take $S_k = S_0 / \{f(x)\}_{x=1}^k$. Then $y_k$ is the lexicographic index of $f(k+1)$ in $S_k$. Note that $y_k$ is always an integer between 1 and $n-k$. Thus you obtain a unique integer between 0 and $n!-1$ for every permutation. To reverse this and find the $i$th permutation is trivial, since $y_0 = (I_P \mbox{ mod } n)+1$, $y_1 = ((I_P-y_0)/n \mbox{ mod } n)+1$ etc., and once all $y_k$ have been calculated, $f(x)$ can be calculated by taking $f(1) = y_0$, which allows you to calculate $S_1$, which in turn gives you $f(2)$, etc.

Thus you have a polynomial time algorithm for converting a permutation of $n$ items into a unique integer between $0$ and $n!-1$ and back.

To pick a new permutation $P_j$, pick a uniformly random integer $x_j$ between $0$ and $n! - j$. Let $A_j = S_0 / \{P_i\}_{i=1}^{j-1}$. Take $P_j$ to be the permutation indexed by the $x_j$ in $A_j$. Repeat as often as necessary (i.e. $m$ times). As $A_j$ only includes the remaining non-redundent permutations, and each permutation is drawn uniformly at random from it, this produces the desired stream of random non-redundent permutations in exact polynomial time.


This answer makes an assumption that it is possible to generate probabilities of the necessary form, which is not necessarily granted in the question. See the answer for Peter Shor for why this can be a problem.

$\endgroup$
  • $\begingroup$ Maybe I'm understanding something wrong, but let me give my comment anyway. "pick a uniformly random integer $x_j$ between 0 and $n!−j$": This seems impossible for a poly-time algorithm, since $n!-j$ is too large when $j << n!$. Moreover, while computing $I_P$, you need to compute $\frac{n!}{(n-i)!}$. Firstly, I think this must be $\frac{n!}{(n-k)!}$, and secondly, it will be superpolynomial in $n$ if $k=n/2$. $\endgroup$ – M.S. Dousti Jun 9 '11 at 18:31
  • $\begingroup$ @Sadeq @Joe: $\frac{n!}{(n-i)!}$ is clearly computable in $n-i$ steps, and can be written in polynomially many bits ($\log n!$ is polynomial in $n$), so I don't see a problem there. but picking a number between $n! -j$ and $0$ seems problematic: it's easy to do in expected $O(\log n!)$ time with rejection sampling, but I don't know about "strict polynomial time". $\endgroup$ – Sasho Nikolov Jun 9 '11 at 18:43
  • $\begingroup$ @Sasho: Thanks for the clarification. Regarding the random choice in strict poly-time, I think the OP has assumed that this is possible. $\endgroup$ – M.S. Dousti Jun 9 '11 at 20:17
  • 1
    $\begingroup$ @Sadeq: that's debatable; he says we can assume a uniform random integer from $[n]$ can be picked in poly time. if the assumption were that for any number $M$, we can assume an subroutine that returns a uniform random integer from $[M]$ and runs in time $\mathsf{poly}(\log M)$, then we'd be good. the whole thing, restriction and assumption, seem a little artificial to me. $\endgroup$ – Sasho Nikolov Jun 9 '11 at 20:22
  • 1
    $\begingroup$ @Sadeq: Indeed, but this is enough to pick an integer between $1$ and $n!$ uniformly at random, as follows: For $k=0$ to $k=n-1$ pick $y_k$ uniformly at random between $0$ and $k$. Then compute $R_n = \sum_{k=0}^{n-1} y_k \frac{n!}{(k+1)!}$. The result is a uniformly random number between $0$ and $n!-1$. However, this may not work for $j\neq 0$. I must admit I missed the requirement that the set be polynomial in $n$. $\endgroup$ – Joe Fitzsimons Jun 10 '11 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.