3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Thank you but where is $n!$? $\endgroup$
    – Turbo
    Aug 15, 2021 at 8:19
  • $\begingroup$ Based on the statements you provide $n!$ is in $FCH$ it appears. Is there a definition for bit-graph? $\endgroup$
    – Turbo
    Aug 15, 2021 at 9:07
  • $\begingroup$ Usually, FCH is defined so that it requires output size to be polynomial. (E.g., this follows from the definition $\mathrm{FCH}=\bigcup_n\mathrm{FC}_n$, where $\mathrm{FC_0=FP}$, $\mathrm{FC}_{n+1}=\mathrm{\#P}^{\mathrm{FC}_n}$.) The bit-graph of a function $f$ is the language $\{(x,i):\mathrm{bit}(f(x),i)=1\}$, where $\mathrm{bit}(w,i)$ is the $i$th bit of $w$. (I take $i$ to be written in binary.) $\endgroup$ Aug 15, 2021 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.