Bounds for constructing $n!$ with additions, subtractions, and multiplications starting from $1$ 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
 A: $t(ak!)$ could have sub-exponential complexity (atleast in a randomized sense) at some $a\in\Bbb N$. Please refer interesting paper http://www.cs.ou.edu/~qcheng/paper/factorial.pdf.
My personal opinion is there is no polynomially many $\{+,-,\times\}$-operation algorithm to construct factorial in a deterministic sense.
However I do believe one of the two possibilities (possibly both) to be true:


*

*The $exp(\sqrt{\log n})$ can be brought to $O((\log n)^c)$ in a randomized sense at a fixed $c>0$.

*No deterministic algorithm can achieve $O((\log n)^c)$ $\{+,-,\times\}$-operations at any fixed $c>0$.
A: The post above has a link to the term-complexity measure based on size of a term
computing a number.  The following different model is from my memory of the BCSS paper, so verification would be appreciated.
For this problem, I define a computation string be a finite sequence of integers $a_i$,
with $ 1  \leq i \leq n$, which obeys the following properties:


*

*$a_1 = 1$

*For every $i$ with $1 \lt i \leq n$, there is an allowed operation (say $++$) and indices $j$ and $k$ with $1 \leq j,k \lt i$ such that $a_i= a_j ++ a_k$.  Note that $j$ can equal $k$.


Then over all such computation strings of varying lengths which contain an integer $s$,
pick the shortest one, say of length $n$, and set $t(s)=n$.
Generally the allowed operations are total and are a fixed finite set, specified in advance.  For the set with addition, subtraction, and multiplication, one can form at
most $(n!)^23^n$ distinct computation strings of length $n+1$, and one can use
associativity and commutativity to cut down on the bound.  It is clear the largest number
formed is $2^{2^n}$ in a computation string of length $n+1$.  It is not clear that one
can arrange a computation of $s$ of length $t(s)$ and at the same time avoid repeats as well as having $a_{i+1}$ depend on $a_i$ for all $1 \lt i \lt n$.  Indeed one may need
to compute two or three numbers of complexity $t$ and put them in the string for later use.
I hope to update this with a small program that does efficient listing of small computation strings, so that one can get an idea of how $t(n!)$ grows with $n$.
EDIT 2015.01.29  Awk code added to generate small computation strings
BEGIN{ SEP= "," ; SEP2 = ";" ; MAX = 40
heap[1]= SEP2 1  #empty computation string followed by possible values for next value
for(newidx=idx=1; newidx < MAX; idx++) {
   # read next computation string and possible next values
   split(heap[idx],stuff,SEP2) ; csqlen=split(substr(stuff[1],1+length(SEP)),csq,SEP)
   vlen=split(stuff[2],vs,SEP)
   for(i=1; i<= vlen; i++) {val=vs[i]
      scsqval=sortme(val); print "Sorted" scsqval
      if ( !(scsqval in db) ) { db[scsqval]=1; outv=""
         addvalues(val,val)
         for(j=1; j <= csqlen; j++) { addvalues((v=csq[j]), val) }
         for(j=1; j <= vlen; j++) { newvals[vs[j]]=1 }      
         ### remove redundant values
         for(j=1; j <= csqlen; j++) { if ((v=csq[j]) in newvals) delete newvals[v] }
         if (val in newvals) delete newvals[val]
         for (v in newvals) { outv = outv SEP v; delete newvals[v] }
         newidx++; heap[newidx] = stuff[1] SEP val SEP2 substr(outv,1+length(SEP))
         print heap[newidx] } }
    for (v in csq) delete csq[v]; for (v in vs) delete vs[v]; for (v in stuff) delete stuff[v]}
}  


function addvalues(a,b) {  newvals[a*b]=newvals[a+b]=newvals[a-b]=newvals[b-a]=1 }

function sortme(vv){ tmps=""
  for(ii=1; ii<=csqlen;ii++) ccsq[ii]=csq[ii]
  ccsq[(newlen=csqlen+1)]=vv
  for(ii=1; ii<=newlen;ii++)  for(jj=ii+1; jj <= newlen; jj++) {
          if (ccsq[ii] > ccsq[jj]) { t=ccsq[jj] ; ccsq[jj]=ccsq[ii] ; ccsq[ii]=t } }
  for(ii=1; ii<=newlen;ii++) {tmps = tmps SEP ccsq[ii] ; delete ccsq[ii] }
  return tmps }

END EDIT 2015.01.29
ADDED 2015.01.30
I am running computations to get strings of length 8.  I invite verification of
the following tuples $(i,t[i])$: (1,1) (2,2) (6,4) (24,5) (120,7) (720,7) (5040,8) .
Of course one has $t[n!]$ is less than $2n$, and by using prime powers and certain
assumptions on the distribution of primes, one can likely prove that for every
$\epsilon$ there is $n_0$ so that for $n > n_0$ one has $t[n!] \lt (1 + \epsilon) n$.  If one did not have subtraction, it might be possible to prove a linear in $n$ lower bound
on $t[n!]$.
The number of computationally distinct terms (I identify permuted strings) follows
the pattern (1,1) (2,2), (3,3) (4,7) (5,25) (6,115) (7,714) (8,x) where x is at least
2403. If anyone verifies these numbers, I invite them to make an OEIS entry.
END ADDED 2015.01.30
Gerhard "Ask Me About Small Programming" Paseman, 2015.01.27
