Found this on Complexity Zoo warning expired certificate
check NP Over The Complex Numbers.
[BCS+97] show the following striking result. For a positive integer $n$, let $t(n)$ denote the minimum number of additions, subtractions, and multiplications needed to construct $n$, starting from 1. If for every sequence ${n_k}$ of positive integers, $t(n_k k!)$ grows faster than polylogarithmically in $k$, then $P_C$ does not equal $NP_C$.
[BCS+97] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation, Springer-Verlag, 1997.
Couldn't find the paper online, so the exact definition would be helpful.
What are bounds for $t(n!)$?
Added later What are bounds for $t(a n!)$ where $a$ is nonzero and no other properties of $a$ are required?
Didn't spend much time, but couldn't solve this:
Find $a>1,k>1$ and $t(a k!) < t(k!)$.
Added I doubt this is of any practical interest because
of the space complexity of factorial.
$$ n\log\left(\frac{n}{e}\right)+1 \leq \log n! $$
In OEIS A025201 a(n) = floor(log(n!))..
We have $n!=\Gamma(n+1)$ and $\log \log \Gamma(2^{1000})=699.6\ldots$
and $\log \log 2^{2^{1000}}=692.7\ldots$.
Even if an oracle computes the factorial, it is impossible to
store in the computer space of all computers on earth.
Added later Comment from Gerhard "Wants To See Better Bounds" Paseman
I'd like to add that a similar sounding problem https://mathoverflow.net/a/75792/3206 using additions and multiplications has easy lower and upper bounds of O(log n). The computation model for this problem is different from the above problem, as "repeated subterms" do not add to the complexity of the computation, to state the matter (from memory) roughly. Gerhard "Wants To See Better Bounds" Paseman, 2015.01.26
References for the above answer in OEIS: http://oeis.org/A005245
Best Answer
If Gerhard Paseman is right that $t(7!)=8$ then $(k,a)=(7,13)$ is already an example of $t(ak!)<t(k!)$, because $$ 13 \cdot 7! = 65520 = 2^{16} - 2^4 $$ can be reached in six steps from $1$: $$ 1 + 1 = 2, \quad 2 \cdot 2 = 4, \quad 4 \cdot 4 = 16, \quad 16 \cdot 16 = 256, \quad 256 \cdot 256 = 65536, $$ and finally $65536 - 16 = 65520$. This also makes $(10,1183)$ a candidate if $10!$ can't be reached as quickly as the seven steps to $65520^2$. [Added later: Michael Stoll now confirms that $t(7!)=8$ $-$ and also reports that it takes nine steps to reach $10!$, and eight for $8!$ and $9!$, so this seven-step route to $65520^2$ gives $t(ak!)<t(k!)$ also for $k=8,9,10$. Later yet, Stoll links to OEIS A217032 which gives the values of $t(k!)-1$ for all $k \leq 19$; this lets us give some more examples, such as $16! \, | \, (2^{64}-2^4)^4$ with $t(16!) = 13$ and $t((2^{64}-2^4)^4) \leq 11$.]
But the asymptotic question is much harder because we don't have good lower bounds on $t(k!)$. Gerhard Paseman gives an upper bound of $2k$ or maybe $(1+o(1))k$, which is within a constant factor of what can be done for any number of this size: if $N < k^k$ we can use $k$ additions to get $1,2,3,\ldots,k$, then $k-1$ multiplications to reach $k^2, k^3, \ldots, k^k$, and then $k+k$ more multiplications and additions to reach $N$ via its base-$k$ expansion. For $t(k!)$ we can reduce this by a factor $\gg \log k$ for large $k$, because $k!$ is a product of powers of the $\pi(k)$ primes $p\leq k$. We can reach all those primes in $\pi(k) + O(k^{1/2})$ additions: let $r = \lfloor \sqrt{k} \rfloor$, then add to get $1,2,3,\ldots,r,2r,3r,\ldots, r^2$, and each prime is a sum of one or two of these. [The Masked Avenger notes that it's a bit faster to first get all the numbers that occur as gaps $p_n - p_{n-1}$, and then get from each prime to the next.] Now use fewer than $\pi(k)$ multiplications to make the products $$ P_i := \prod_{ip \leq k < (i+1) p} p $$ for $i=1,2,3,\ldots,r$, and then $k! = P_1^{\phantom 1} P_2^2 P_3^3 \cdots P_r^r$ times $\pi(r)$ prime powers.
If that approach were optimal then we could get $t(ak!) < t(k!)$ by replacing $\prod_{i=1}^r P_i^i$ by $\left(\prod_{i=1}^r P_i\right)^{2^\rho}$ once $2^\rho \geq r$. But it seems that in fact $t(k) \ll k^{1/2 + o(1)}$ because one can write $m^2! = \prod_{j=0}^{m-1} Q(jm)$ where $Q(X) = (X+1) (X+2) (X+3) \cdots (X+m)$ and use FFT-like tricks to evaluate a degree-$m$ polynomial at $m$ points in only $m \log^A m$ operations. (See for instance this page. I learned of this surprising fact some year back from Henry Cohn. Caveat: some more work might be needed to fit this method into the $\{+,-,\times\}$ model without losing a factor worse than $k^\epsilon$. Added later: Turbo notes that this paper by Q.Cheng (of which more in the next paragraph) cites a paper by Strassen from the 1970's that gives a route to $k!$ in $O(k^{1/2} \log^2 k)$ $\{+,-,\times\}$ steps.)
This might be asymptotically optimal, but proving $t(k!) \gg k^{1/2}$ (or even $t(k) \gg k^\theta$ for some $\theta>0$) seems to be beyond reach. Meanwhile, Lenstra's ECM (elliptic curve method) for factoring suggests that $t(ak!)$ can be as small as $\exp O(\sqrt{\log k\,})$. Turbo gave this link to a 2004 paper by Qi Cheng that spells out this connection; that's perhaps surprisingly late, since Lenstra's ECM paper dates back to 1987 $-$ I found some e-mails from 1996 where I noted that ECM suggests that some multiple of $k!$ can be computed in a number of operations subexponential in $\log k$, and I wouldn't be surprised if Lenstra himself noticed this some years earlier. Note that likewise the counterexamples involving $2^{16}-2^4$ etc. that I started with are in effect using Pollard's $p-1$ factorization method.
I tried to estimate how well this would work for $k = 10^7$ compared with the prime-factorization technique. There are $664579$ primes $p < 10^7$, so any route to $k!$ via prime factorization would have to take at least $2 \cdot 664579$ steps (one to reach each $p$ and one to multiply by it).
For the ECM approach to some multiple of $k!$, I tried the following experiment. For each of the first $96$ isogeny classes of rank-$1$ elliptic tables in Cremona's table (these being the first two columns of Table 2 on page 235 of his Algorithms for Modular Elliptic Curves, covering conductors $N \leq 220$), choose a curve $E_i$ and a generator $P_i$ ($i \leq 96$). Then, for each prime $p \leq 10^7$, factor the order of each $P_i \bmod p$ using the built-in gp command ellorder, factor it as $\prod_j l_j^{e_j}$, and note the minimal value $m(p)$ of $\max_j l_j^{e_j}$ over the $96$ choices of $(E_i,P_i)$; thus for each $p$ there's some $i$ for which the order of $P_i \bmod p$ is a product of prime powers $\leq m(p)$. This took a few hours. The largest $m(p)$ observed is $379$, for $p = 6978421$. But about 90% of these primes have $m(p) \leq 83$. (There are $67608$ primes $p\leq 10^7$ with $m(p)>83$; also $47193$ with $m(p)>100$ and $22518$ with $m(p)>113$.) There are $23$ primes $l \leq 83$; let $M = 2^6 3^4 5^2 7^2 \prod_{l=11}^{83} l$, and compute for each $i$ a nonzero multiple $D_i$ of the denominator of $M P_i$, which requires about $150$ group-law additions in $E_i$ because $M \approx 2^{122.6}$. Then form $\prod_{i=1}^{96} D_i$, multiply by the product of the $67608$ missing primes, and square the whole thing $23$ times to get a multiple of $10^7!$. I don't know how many arithmetic operations it takes these days to do an elliptic-curve addition or subtraction, but it must be under $40$, and this already puts us under half our estimate for computing $10^7!$ itself via prime factorization ($96 \cdot 150 \cdot 40 = 600000$). There's probably a significant additional factor to be saved by using more curves $E_i$, balancing the $m(p)$ cutoff, and choosing $E_i$ that allow for faster group operations such as Edwards curves.