On the complexity of factorial ratios Given two polynomials $p(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$ and $q(y_1,\dots,y_m)\in\mathbb Z[y_1,\dots,y_m]$ and $n+m$ positive integers $a_1,\dots,a_n,b_1,\dots,b_m$ where:

*

*degree of the polynomials


*number of bits in coefficients of the polynomials


*the number of bits in integers $a_i$


*the number of bits in integers $b_j$


*$n,m$
are all polynomial in $t$ (a parameter).
The problem is to decide if
$$\frac{p(a_1!,\dots,a_n!)}{q(b_1!,\dots,b_m!)}$$
is an integer.


*

*Is the problem in time complexity $O(poly(t))$ in worst case scenario?


*What is the complexity class in which the problem lies in?

 A: I claim that there is an algorithm for factorizing integers that runs in polynomial time if it has access to an oracle that states whether $\frac{p(a_{1}!,\dots,a_{n}!)}{q(b_{1}!,\dots,b_{n}!)}$ is an integer or not.
Suppose that $x$ is a positive integer that one seeks to factorize. Wilson's theorem states that $x$ is prime if and only if $(x-1)!=-1\bmod x$. Using Wilson's theorem, this oracle can determine whether $x$ is a prime number or not. Primality testing runs in polynomial time so we don't even need Wilson's theorem. If $x$ is a composite number, then one can use this algorithm to return a factor of $x$ that is not $1$ or $x$ using the following technique. By repeatedly using the oracle, one first finds the least natural number $n$ such that $x$ is a factor of $n!$. The process of finding the number $n$ requires one to access the oracle $O(\mathsf{log}(n))$
many times. Therefore, since $x$ is a factor of $n!$ but $x$ is not a factor of $(n-1)!$, we know that $n$ and $x$ have a common factor, so we compute $\mathsf{gcd}(x,n)$.
There are no known polynomial time factorization algorithms. Since the security of many cryptographic algorithms depends on the fact that factorization is difficult, we know that people are confident that there is probably not a polynomial time factorization algorithm, so I doubt that the problem of determining whether $\frac{p(a_{1}!,\dots,a_{n}!)}{q(b_{1}!,\dots,b_{n}!)}$ is an integer or not is in polynomial time. However, since factorization lies in BQP (the analogue of P for quantum computation), this answer does not preclude the problem of determining whether $\frac{p(a_{1}!,\dots,a_{n}!)}{q(b_{1}!,\dots,b_{n}!)}$ is an integer lies in $\mathsf{BQP}$.
