<p>Few years back a <a href="https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring?rq=1">question</a> 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.</p>

<p>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?</p>

CC BY-SA 3.0
2015-06-18T09:21:31.203Z
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
CC BY-SA 3.0
2015-06-18T09:33:46.583Z
what is an unary bound?
Turbo
CC BY-SA 3.0
2015-06-18T10:01:17.187Z
A bound that can be written in unary. Here, wlog $u$ is at most the degree of $p$.
Emil Jeřábek
CC BY-SA 3.0
2015-06-18T13:03:32.513Z
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
CC BY-SA 3.0
2015-06-18T13:12:41.930Z
https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution
Emil Jeřábek
<polynomials><np-complete>
Complexity of variant polynomial factorization
Turbo
# Complexity of variant polynomial factorization

(Asked by: username_0 on 2015-06-17)

Few years back a [question](https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring?rq=1) 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?

**Tags:** polynomials, np-complete
> **Comments:**
> **username_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.  
> **username_0**: what is an unary bound?  
> **username_1**: A bound that can be written in unary. Here, wlog $u$ is at most the degree of $p$.  
> **username_0**: 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?  
> **username_1**: https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution  

---

## 0 answers

