Skip to main content
Corrected the result of [1].
Source Link
Hhan
  • 561
  • 5
  • 8

The thing that you are asking is the required number of integer operations for computing $N!$ starting only from $1$ and $N$, which is usually referred to as the straight-line complexity of $N!$ denoted by $\tau(N!)$. (or BSS model, though I am not sure they are indeed equivalent; they are at least highly related.)

And your main question can be rephrased in terms of the standard big-O notation as follows: $$ \tau(N!) = \Omega(N), \text{ or } \tau(N!) =O(N^{1-\epsilon}) \text{ for some constant }\epsilon? $$

The answer is the latter. Indeed, there is a known algorithm showing $\tau(N!)=O(N^{0.5})$$\tau(N!)=O(\sqrt{N}\log^2 N)$ and evenif we just want to find a $\tau(N!)$multiple of $N!$ then there is a subexponential onalgorithm $\log N$, though I never checked about the algorithms.

The most relevant references I know are as follows:

  1. "On the Ultimate Complexity of Factorials" by Qi Cheng, which shows the subexponential algorithm for computing a multiple of factorial,
  2. "ON THE INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ AND AN ALGEBRAIC VERSION OF “NP != P?”" by Michael Shub and Steve Smale, which emphasizes this problem.

In fact, according to the second reference, the complexity of factorial is indeed an important problem known to be connected to the algebraic version of the P=NP problem. Namely, if any multiplication of $N!$ cannot be computed in time $O({\rm poly}\log(N))$, then the algebraic version of $P\neq NP$ is true.

The thing that you are asking is the required number of integer operations for computing $N!$ starting only from $1$ and $N$, which is usually referred to as the straight-line complexity of $N!$ denoted by $\tau(N!)$. (or BSS model, though I am not sure they are indeed equivalent; they are at least highly related.)

And your main question can be rephrased in terms of the standard big-O notation as follows: $$ \tau(N!) = \Omega(N), \text{ or } \tau(N!) =O(N^{1-\epsilon}) \text{ for some constant }\epsilon? $$

The answer is the latter. Indeed, there is a known algorithm showing $\tau(N!)=O(N^{0.5})$ and even $\tau(N!)$ is subexponential on $\log N$, though I never checked about the algorithms.

The most relevant references I know are as follows:

  1. "On the Ultimate Complexity of Factorials" by Qi Cheng which shows the subexponential algorithm,
  2. "ON THE INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ AND AN ALGEBRAIC VERSION OF “NP != P?”" by Michael Shub and Steve Smale, which emphasizes this problem.

In fact, according to the second reference, the complexity of factorial is indeed an important problem known to be connected to the algebraic version of the P=NP problem. Namely, if any multiplication of $N!$ cannot be computed in time $O({\rm poly}\log(N))$, then the algebraic version of $P\neq NP$ is true.

The thing that you are asking is the required number of integer operations for computing $N!$ starting only from $1$ and $N$, which is usually referred to as the straight-line complexity of $N!$ denoted by $\tau(N!)$. (or BSS model, though I am not sure they are indeed equivalent; they are at least highly related.)

And your main question can be rephrased in terms of the standard big-O notation as follows: $$ \tau(N!) = \Omega(N), \text{ or } \tau(N!) =O(N^{1-\epsilon}) \text{ for some constant }\epsilon? $$

The answer is the latter. Indeed, there is a known algorithm showing $\tau(N!)=O(\sqrt{N}\log^2 N)$ and if we just want to find a multiple of $N!$ then there is a subexponential algorithm $\log N$, though I never checked about the algorithms.

The most relevant references I know are as follows:

  1. "On the Ultimate Complexity of Factorials" by Qi Cheng, which shows the subexponential algorithm for computing a multiple of factorial,
  2. "ON THE INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ AND AN ALGEBRAIC VERSION OF “NP != P?”" by Michael Shub and Steve Smale, which emphasizes this problem.

In fact, according to the second reference, the complexity of factorial is indeed an important problem known to be connected to the algebraic version of the P=NP problem. Namely, if any multiplication of $N!$ cannot be computed in time $O({\rm poly}\log(N))$, then the algebraic version of $P\neq NP$ is true.

Source Link
Hhan
  • 561
  • 5
  • 8

The thing that you are asking is the required number of integer operations for computing $N!$ starting only from $1$ and $N$, which is usually referred to as the straight-line complexity of $N!$ denoted by $\tau(N!)$. (or BSS model, though I am not sure they are indeed equivalent; they are at least highly related.)

And your main question can be rephrased in terms of the standard big-O notation as follows: $$ \tau(N!) = \Omega(N), \text{ or } \tau(N!) =O(N^{1-\epsilon}) \text{ for some constant }\epsilon? $$

The answer is the latter. Indeed, there is a known algorithm showing $\tau(N!)=O(N^{0.5})$ and even $\tau(N!)$ is subexponential on $\log N$, though I never checked about the algorithms.

The most relevant references I know are as follows:

  1. "On the Ultimate Complexity of Factorials" by Qi Cheng which shows the subexponential algorithm,
  2. "ON THE INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ AND AN ALGEBRAIC VERSION OF “NP != P?”" by Michael Shub and Steve Smale, which emphasizes this problem.

In fact, according to the second reference, the complexity of factorial is indeed an important problem known to be connected to the algebraic version of the P=NP problem. Namely, if any multiplication of $N!$ cannot be computed in time $O({\rm poly}\log(N))$, then the algebraic version of $P\neq NP$ is true.