0

Few years back a question on whether a variant of integer factorization was $\mathsf{NP}$ complete was asked, which according to state of mathematics today does not have a conclusive answer.

Is following variant of polynomial factorization, 'given $p(x)\in\Bbb Z[x], l,u\in\Bbb N$, is there a $q(x)\in\Bbb Z[x]$ with $l\leq\mathsf{deg}(q(x))\leq u$ such that $q(x)|p(x)$', $\mathsf{NP}$ complete?

Community
  • 1
Turbo
  • 12,812
  • 1
  • 19
  • 68
  • 1
    No, it's in P. Factoring of polynomials over $\mathbb Z$ into irreducible factors (except constant factors) can be done in polynomial-time by LLL, and then the question reduces to checking if a subset of the degrees of the irreducible factors sums to a number between $l$ and $u$, which is easy as they have a unary bound. – Emil Jeřábek Jun 18 '15 at 09:21
  • what is an unary bound? – Turbo Jun 18 '15 at 09:33
  • A bound that can be written in unary. Here, wlog $u$ is at most the degree of $p$. – Emil Jeřábek Jun 18 '15 at 10:01
  • Oh the issue here is we have atmost $O(p)$ distinct degree of factors and checking certain subset of degrees sum in between $l$ and $u$ can be done in $O(p^c)$ time for some fixed constant $c>1$? This is in poly time? – Turbo Jun 18 '15 at 13:03
  • https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution – Emil Jeřábek Jun 18 '15 at 13:12

0 Answers0