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 http://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

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

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!)$?

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 http://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

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 http://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

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 is lower bound for $t(n!)$?

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 http://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

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!)$?

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 http://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