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.



Is factorial computation known to be in a class smaller than $FEXP$?
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](https://doi.org/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).


