<p>One approach on this question, related to complexity-theoretic questions, is due to Shub and Smale [1] who proved that if $n!$ is <em>ultimately hard</em> 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 <em>ultimately hard</em> means that the number of operations needed is asymptotically not bounded by some polynomial in $\log n$. </p>

<p>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 <em>standard</em> 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.</p>

<p>[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.</p>

<p>[2]  Qi Cheng, <a href="http://www.cs.ou.edu/~qcheng/paper/factorial.pdf">On the Ultimate Complexity of Factorials</a>, Theoretical Computer Science, Volume 326, Issues 1-3, Pages 419-429. </p>

CC BY-SA 3.0
2014-10-21T07:46:57.727Z
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.
Harry
CC BY-SA 3.0
2014-10-20T19:32:58.833Z
2014-10-20T19:45:28.900Z
2014-10-20T19:45:28.900Z
Bruno
<p>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. </p>

<p>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, <a href="https://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/181#181">see here</a>, and we are trying to put Factorization inside $\mathrm{P}$.</p>

<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 <a href="https://cstheory.stackexchange.com/questions/2204/efficiently-getting-bits-of-n/2206#2206">here</a> and the <a href="http://en.wikipedia.org/wiki/Factorial" rel="nofollow noreferrer">wiki article</a> from the far away 1983. </p>

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

<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!$ ?</p>

CC BY-SA 3.0
2014-10-20T19:07:23.127Z
What are the sizes of the input and the output?
usul
CC BY-SA 3.0
2014-10-20T20:43:23.733Z
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.
Emil Jeřábek
<lower-bounds><factoring>
Complexity lower bound of finding the factorial of a number
Harry
# Complexity lower bound of finding the factorial of a number

(Asked by: username_0 on 2014-10-20)

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](https://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/181#181), 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](https://cstheory.stackexchange.com/questions/2204/efficiently-getting-bits-of-n/2206#2206) and the [wiki article](http://en.wikipedia.org/wiki/Factorial) 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!$ ?

**Tags:** lower-bounds, factoring
> **Comments:**
> **username_1**: What are the sizes of the input and the output?  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2014-10-20. Score: 13 | Accepted answer

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](http://www.cs.ou.edu/~qcheng/paper/factorial.pdf), Theoretical Computer Science, Volume 326, Issues 1-3, Pages 419-429.

> **Comments:**
> **username_0**: 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.  

---

