0
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jun 18 '15 at 9:21
  • $\begingroup$ what is an unary bound? $\endgroup$ – T.... Jun 18 '15 at 9:33
  • $\begingroup$ A bound that can be written in unary. Here, wlog $u$ is at most the degree of $p$. $\endgroup$ – Emil Jeřábek Jun 18 '15 at 10:01
  • $\begingroup$ 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? $\endgroup$ – T.... Jun 18 '15 at 13:03
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – Emil Jeřábek Jun 18 '15 at 13:12

Your Answer

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

Browse other questions tagged or ask your own question.