2
$\begingroup$

I was wondering about the complexity of the factorial of a number mostly because this problem is not referenced in the complexity books I have read.

Two similar problems, Matrix Multiplication and Factorization are in, almost, all discussions about $\mathrm{P}$ and $\mathrm{NP}$. The complexity of the first is a major research field, see here, and we are trying to put Factorization inside $\mathrm{P}$.

But for the, seemingly, close problem of Factorial nothing is being said. Almost no result at all. The only one I could find is the one mentioned here and the wiki article from the far away 1983.

Why there is no interest in it? Can it have any implications in Complexity Theory like Factoring? Can Factorial be in $\mathrm{P}$ ?

Lastly one thought, Factorial must be in $\mathrm{NP}$ (or better in $\mathrm{FNP}$?) the certificate would be the actual number? that is $n!$ ?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ What are the sizes of the input and the output? $\endgroup$
    – usul
    Oct 20, 2014 at 19:07
  • 8
    $\begingroup$ Factorial has nothing to do with NP or FNP (in the standard computation model, as opposed to algebraic complexity as in Bruno’s answer). If the input is given in unary, it is computable in essentially linear time (as already mentioned in the WP article). If the input is given in binary, the output is exponentially larger than the input, so it needs exponential time. $\endgroup$
    – Emil Jeřábek
    Oct 20, 2014 at 20:43

1 Answer 1

Reset to default
13
$\begingroup$

One approach on this question, related to complexity-theoretic questions, is due to Shub and Smale [1] who proved that if $n!$ is ultimately hard to compute, then $\mathsf{VP}\neq\mathsf{VNP}$ over some field. Their model of computation is the straight-line programs: The goal is to compute $n!$ from the constant $1$, using only additions, subtractions and multiplications. That $n!$ is ultimately hard means that the number of operations needed is asymptotically not bounded by some polynomial in $\log n$.

For more recent results in this direction (and pointers to the relevant literature), you can read a paper of Cheng [2]. The paper contains also a very brief remark about the standard complexity of the problem, that has to be exponential in $\log n$ (because of the output size), and of the modular variant of it (computing $n! \bmod m$) and its relations with integer factoring.

[1] Mike Shub and Stephen Smale. On the intractability of Hilbert’s nullstellensatz and an algebraic version of “P=NP?”. Duke Math. J., 81:47–54, 1995.

[2] Qi Cheng, On the Ultimate Complexity of Factorials, Theoretical Computer Science, Volume 326, Issues 1-3, Pages 419-429.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow, rookie mistake. Thanks @bruno and Emil. Last night couldn't think that, by definition of the problem, the output must always be exponentially bigger than the input. As I realize from the first part of your answer, there are no known lower bound for computing the factorial. $\endgroup$
    – Harry
    Oct 21, 2014 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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