1
$\begingroup$

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:

  1. degree of the polynomials

  2. number of bits in coefficients of the polynomials

  3. the number of bits in integers $a_i$

  4. the number of bits in integers $b_j$

  5. $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.

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

  2. What is the complexity class in which the problem lies in?

$\endgroup$
3
  • $\begingroup$ Can you evaluate the numerator & denominator in polynomial time? If you can, then you can apply Euclid's algorithm to work out whether the quotient is an integer. $\endgroup$ May 23 at 7:24
  • $\begingroup$ Corrected the mistake. $\endgroup$
    – Mr.
    May 23 at 8:19
  • 1
    $\begingroup$ A very special case of this problem is to determine if $\frac{(p-1)!+1}{p}$ is an integer, which is equivalent to $p$ being prime. Of course this is known to be polynomial-time solvable, but is already very nontrivial. I doubt much is known in the general case. $\endgroup$
    – Wojowu
    May 23 at 13:08
3
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ I think the problem probably can count number of factors in an interval and factoring might be one application. $\endgroup$
    – Mr.
    May 23 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.