Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I ran into tricky issues in computing time complexity of the permutation generator algorithm, and had great difficulty convincing a friend (experienced in Theoretical CS) of the validity of my reasoning. I'd like to clarify this here.

Tricky complexity question Given a positive integer $n$, what is the time complexity of generating all permutations on the set $[n]=\{1,2,..,n\}$?

Friend's reasoning Any algorithm to generate all permutations of $[n]$ takes $\Omega(n!)$ time. This is a provable , super-exponential lower bound, [edited ]hence the problem is in EXPTIME.

My reasoning The above reasoning is correct, except that one should compute the complexity with respect to the number of expected output bits. Here, we expect $n!$ numbers in the output, and each can be encoded in $\log n$ bits; hence we expect $b=O(n!\log n)$ output bits. A standard algorithm to traverse all $n!$ permutations will take a polynomial time overhead i.e. it will execute in $s(n)=O(n!n^k)$ time, hence we will need $t(n)=b(n)+s(n) = O(n!(\log n + n^k)) $ time in all.

Since $b(n)$ is the number of output bits, we will express $t(n)$ as a function of $b(n)$. To do so, note that $n^k \approx (n!)^{k/n}$ using $n! \approx n^n$; so $s(n)=O( b(n) (b(n))^{k/n}) = O(b^2(n) )$ . Hence we have a polynomial time algorithm in the number of output bits, and the problem should be in $P$, not in say EXPTIME.

Main Question : Whose reasoning is correct, if at all?

Note I raised this problem here because I had a bad experience at StackOverflow with a different tricky time complexity problem; and this is certainly not suited for Cstheory.SE as it isn't research level.

share|improve this question
2  
Why compare the time with the number of output bits? –  André Nicolas Oct 26 '11 at 6:16
4  
"This is a provable, super-exponential lower bound, hence the problem is NP-Hard." This is what NP-hard does not mean (i.e., neither NP nor NP-hard means non-polynomial). :-) –  Srivatsan Oct 26 '11 at 6:21
    
A problem being in E implies that it is also NP-Hard. NP-Hard doesn't imply non-polynomial, but non-polynomial does imply NP-Hard, which is what he said. It is a silly way to put it and I think it's a good edit, but it wasn't technically wrong. –  Keith Irwin Oct 26 '11 at 7:15
1  
@Keith I am afraid you got it all wrong. A problem is in E does not imply it is NP-hard. For e.g., $P \subseteq E$, but it is believed that no problem in P is NP-hard. Neither does non-polynomiality imply NP-hardness. Non-polynomial simply means that the problem is not in P. There are certainly NP-intermediate languages, that are neither in P nor NP-complete (of course, assuming P $\neq$ NP). –  Srivatsan Oct 26 '11 at 7:27
1  
Sorry, I really didn't say that clearly. Where I said "A problem being in E", I really meant "Being strictly in E", that is, being in E and not being in any complexity classes which are strict subsets of E. –  Keith Irwin Oct 26 '11 at 21:21

4 Answers 4

up vote 4 down vote accepted

When classifying problems, they are not classified according to the size of the output, in bits, but rather, the size of the input. The size of the input is the size of the problem, which is the size we care about when defining standard complexity classes. Problems in P take time bounded by a polynomial function of the problem size. Problems in P-SPACE take space bounded by a polynomial function of the problem size. Problems in E take time bounded by an exponential function of the problem size, and so on. If the size of the output is exponential in the size of the input problem, (which, in this case would be the initial set), then it's clear that the problem must be, at minimum, exponential.

If you wish to define your own classification of problems (POUT-TIME and POUT-SPACE or something) in terms of the size of the output, you are welcome to, but this is not how standard complexity classes are defined. Your friend is correct.

share|improve this answer
2  
“When classifying problems, they are not classified according to the size of the output, in bits, but rather, the size of the input.” This claim is too strong to be true. When we study enumeration problems (such as the one in the question), considering the time complexity in terms of output size is very common. On the other hand, you are right in that complexity classes P and EXP are defined in terms of the time complexity as a function of the input size. (Here I put aside the fact that they are usually defined as classes of decision problems instead of enumeration problems.) –  Tsuyoshi Ito Oct 26 '11 at 17:46

Your friend's bound is rather weak. Let the input number be $x$. Then the output is $x!$ permutations, but the length of each permutation isn't $x$ bits, as you claim, but $\Theta(\lg(x!)) = \Theta(x \lg x)$ bits. Therefore the total output length is $\Theta(x! \;x \lg x)$ bits.

But, as @KeithIrwin has already pointed out, complexity classes work in terms of the size of the input. An input value of $x$ has size $n=\lg x$, so the generation is $\Omega(2^n! \;2^n n)$.

share|improve this answer
    
The fact that the bound is weak doesn't invalidate the reasoning. –  Ganesh Nov 5 '11 at 7:08

I wish to substantially refine Keith Irwin's answer as follows.

Given a class of problems $\mathcal{P}$, the solution to each of which can be computed in polynomial time in the size of their inputs. This does not mean that $\mathcal{P}$ lies in the complexity class $\mathsf{P}$. Why not? Because $\mathsf{P}$ admits only decision problems !

For example, suppose $\mathcal{P}$ is that class of problems that provides as input a positive integer $n$ and asks the value of $n+1$ as output. It's easy to see that $\mathcal{P}$ can be solved in polynomial time in input size. But $\mathcal{P} \not \subset \mathsf{P}$, for $\mathcal{P}$ does not consist of decision problems at all! Instead $\mathcal{P}$ is a set of function problems; it lies in $\mathsf{FP}$, that class of functions computable in poly time.

Similarly, the permutation generator takes input $n$ and provides a function $f(n)$ as output; it does not decide anything. Hence, regardless of its complexity, it does not belong in $\mathsf{P}$. It's more meaningful to think of the permutation generation problem as a function problem. The provable super exponential bound mentioned in the question prevents the generation problem from lying in $\mathsf{FP}$. Perhaps $\mathsf{FEXP}$ would be a better answer, though I'm not sure. As Keith said,using the number of output bits as a measure of complexity needs new definitions of complexity classes that take output size into question.

Note that it's certainly meaningful to make decision versions of the permutation generation problem, such as:

Given integers $(n,k)$, what is the $k$-th bit of the output of the permutation generator on $[n]$?

This particular problem is indeed in $\mathsf{P}$, for the $k$th bit can be computed by efficient permutation unranking.

share|improve this answer

In the analysis of algorithms there are different cost models.

The most common ones are (quote from Wikipedia):

  • the uniform cost model, also called uniform-cost measurement (and similar variations), assigns a constant cost to every machine operation, regardless of the size of the numbers involved
  • the logarithmic cost model, also called logarithmic-cost measurement (and variations thereof), assigns a cost to every machine operation proportional to the number of bits involved

I guess the complexities you gave use a different model and therefore can not be compared, they can both be correct.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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