Is factorial computation known to be in a class smaller than $FEXP$? Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of constants and arbitrary number of integer variables to compute $n!$.

In terms of output size $n!$ is not even in polynomial in $log(n)$ space. So in terms of Boolean complexity where is the computation of $n!$ in? It is clearly not in $FCH$ but in $FEXPSPACE$.


If we are given a prime $p$ is the computation of $n!\bmod p$ in $FCH$?


Will the answers change much if there is a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of constants and arbitrary number of integer variables to compute $n!$?

A sequence of arithmetic operations is referred as a straightline program.
 A: Yes, $n!\bmod p$ is computable in FCH. More generally, if $f$ is a polynomial-time computable function, then given $n$ and $m$ in binary, we can compute
$$\prod_{i<n}f(i)\bmod m\tag1$$
in FCH. This follows from the fact that if we are given in unary $n$, $m$, and a sequence of numbers $a_0,\dots,a_{n-1}$, then we can compute
$$\prod_{i<n}a_i\bmod m$$
in uniform $\mathrm{TC}^0$, which was proved by

William Hesse, Eric Allender, and David A. Mix Barrington: Uniform   constant-depth threshold circuits for division and iterated multiplication,  Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695–716, doi 10.1016/S0022-0000(02)00025-9.

In fact, we can avoid almost all the intricate machinery of the [HAB02] paper due to a combination of two factors:

*

*When the algorithms are exponentially scaled to FCH, we only need quasipolynomial $\mathrm{TC}^0$. Thus, for example, we can use the trivial polynomial-time algorithm for modular exponentiation by repeated squaring instead of the [HAB02] algorithm (which actually puts it in the linear-time hierarchy).


*Since the result is computed modulo $m$, we don’t need the full force of Chinese Remainder Reconstruction (which is the most complicated and most costly step in [HAB02]).
So, here is an explicit algorithm. First, if $m=p$ is prime, we have
$$\prod_{i<n}f(i)\equiv g^{\sum_{i<n}d(f(i))}\pmod p,$$
where $g$ is a generator of $\mathbb F_p^\times$, and $d$ is the inverse of $g^x\bmod p$ (i.e., discrete logarithm). (Let’s consider that $d(0)=-\infty$.) We can compute $g$ and $d(f(i))$ in FPH, thus $\sum_id(f(i))$ in $\mathrm{\#P^{PH}}$, thus the final result in
$$\mathrm{FP^{\#P^{PH}}=FP^{\#P}=FP^{PP}}.$$
(I’m using here the fact that $\mathrm{\#P^{PH}\subseteq P^{\#P}}$.)
A similar argument works when $m$ is a prime power.
For general $m$, we can compute the prime factorization $m=\prod_{j<k}p_j^{e_j}$ in FPH, thus (for each $j<k\le\log n$) $r_j=\prod_{i<n}f(i)\bmod p_j^{e_j}$ (or rather, the pair $(p_j^{e_j},r_j)$) in $\mathrm{FP^{\#P^{PH}}=FP^{PP}}$ as above, and we can reconstruct the result modulo $m$ in polynomial time. Thus again, the overall complexity is that we can compute (1) in
$$\mathrm{FP^{PP}}.$$

The non-modular function $n!$ as such is an exponential-output-size function whose bit-graph is computable in CH (again, by [HAB02]). There is no common name for this class of functions, as far as I am aware. It is included in FPSPACE, as long as you make sure not to artificially restrict this class to functions with polynomial output size (for space classes, it is a standard definition that space usage only counts work tapes, not the read-only input tape or the write-only output tape).
