Sí, $n!\bmod p$ es computable en FCH. Más generalmente, si $f$ es una función computable en tiempo polinómico, entonces dado $n$ y $m$ en binario, podemos calcular $$\prod_{i<n}f(i)\bmod m\tag1$$ en FCH. Esto se deduce del hecho de que si se nos da en unario $n$ , $m$ y una secuencia de números $a_0,\dots,a_{n-1}$ entonces podemos calcular $$\prod_{i<n}a_i\bmod m$$ con el uniforme $\mathrm{TC}^0$ , lo que fue demostrado por
William Hesse, Eric Allender y David A. Mix Barrington: Circuitos de umbral uniforme de profundidad constante para la división y la multiplicación iterada Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695-716, doi 10.1016/S0022-0000(02)00025-9 .
De hecho, podemos evitar casi toda la intrincada maquinaria del artículo [HAB02] debido a una combinación de dos factores:
-
Cuando los algoritmos se escalan exponencialmente a FCH, sólo necesitamos quasipolinomio $\mathrm{TC}^0$ . Así, por ejemplo, podemos utilizar el algoritmo trivial de tiempo polinómico para la exponenciación modular por cuadratura repetida en lugar del algoritmo [HAB02] (que en realidad lo sitúa en la jerarquía de tiempo lineal).
-
Dado que el resultado se calcula en módulo $m$ no necesitamos toda la fuerza de la Reconstrucción del Resto Chino (que es el paso más complicado y más costoso en [HAB02]).
Por lo tanto, aquí hay un algoritmo explícito. Primero, si $m=p$ es prime tenemos $$\prod_{i<n}f(i)\equiv g^{\sum_{i<n}d(f(i))}\pmod p,$$ donde $g$ es un generador de $\mathbb F_p^\times$ y $d$ es la inversa de $g^x\bmod p$ (es decir, logaritmo discreto). (Consideremos que $d(0)=-\infty$ .) Podemos calcular $g$ y $d(f(i))$ en FPH, así $\sum_id(f(i))$ en $\mathrm{\#P^{PH}}$ por lo que el resultado final en $$\mathrm{FP^{\#P^{PH}}=FP^{\#P}=FP^{PP}}.$$ (Estoy utilizando aquí el hecho de que $\mathrm{\#P^{PH}\subseteq P^{\#P}}$ .)
Un argumento similar funciona cuando $m$ es una potencia primera.
En general $m$ podemos calcular la factorización en primos $m=\prod_{j<k}p_j^{e_j}$ en FPH, por lo que (para cada $j<k\le\log n$ ) $r_j=\prod_{i<n}f(i)\bmod p_j^{e_j}$ (o más bien, el par $(p_j^{e_j},r_j)$ ) en $\mathrm{FP^{\#P^{PH}}=FP^{PP}}$ como en el caso anterior, y podemos reconstruir el resultado en módulo $m$ en tiempo polinómico. Así, de nuevo, la complejidad global es que podemos calcular (1) en $$\mathrm{FP^{PP}}.$$
La función no modular $n!$ como tal es una función de tamaño de salida exponencial cuyo gráfico de bits es computable en CH (de nuevo, por [HAB02]). No hay un nombre común para esta clase de funciones, hasta donde yo sé. Está incluida en FPSPACE, siempre y cuando te asegures de no restringir artificialmente esta clase a funciones con tamaño de salida polinómico (para las clases de espacio, es una definición estándar que el uso de espacio sólo cuenta las cintas de trabajo, no la cinta de entrada de sólo lectura o la cinta de salida de sólo escritura).
