<p>Given $N(x)\in\Bbb Z_{\geq0}[x]$ with non-negative coefficients with promise that there exists $a(x),b(x),c(x),d(x)\in\Bbb Z_{\geq0}[x]$ with non-negative coefficients such that $N(x)=a(x)b(x)+c(x)d(x)$ with $\mathsf{deg}(a(x)b(x))=\mathsf{deg}(c(x)d(x))=\mathsf{deg}(N(x))$, $\mathsf{deg}(a(x))=\mathsf{deg}(b(x))=\mathsf{deg}(c(x))=\mathsf{deg}(d(x))=\frac{\mathsf{deg}(N(x))}2$, what is the complexity of decomposing $N(x)$? Assume that each coefficient of constituent polynomials could be represented using $n$ bits.</p>

<p>If there are many quadruples $a(x),b(x),c(x),d(x)$, finding one suffices.</p>

CC BY-SA 3.0
2015-06-03T23:48:09.853Z
We need a little more context: what does "decomposing" mean here? Is it finding $a,b,c$? What if there exist several such polynomials?
cody
CC BY-SA 3.0
2015-06-04T01:01:15.547Z
Yes finding $a,b,c,d$.
Turbo
CC BY-SA 3.0
2015-06-04T01:10:58.237Z
Finding one quadruple in $\Bbb Z_{\geq0}[x]$ suffices.
Turbo
<algebraic-complexity><polynomials>
Polynomial decomposition complexity
Turbo
# Polynomial decomposition complexity

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

Given $N(x)\in\Bbb Z\_{\geq0}[x]$ with non-negative coefficients with promise that there exists $a(x),b(x),c(x),d(x)\in\Bbb Z\_{\geq0}[x]$ with non-negative coefficients such that $N(x)=a(x)b(x)+c(x)d(x)$ with $\mathsf{deg}(a(x)b(x))=\mathsf{deg}(c(x)d(x))=\mathsf{deg}(N(x))$, $\mathsf{deg}(a(x))=\mathsf{deg}(b(x))=\mathsf{deg}(c(x))=\mathsf{deg}(d(x))=\frac{\mathsf{deg}(N(x))}2$, what is the complexity of decomposing $N(x)$? Assume that each coefficient of constituent polynomials could be represented using $n$ bits.

If there are many quadruples $a(x),b(x),c(x),d(x)$, finding one suffices.

**Tags:** algebraic-complexity, polynomials
> **Comments:**
> **username_1**: We need a little more context: what does "decomposing" mean here? Is it finding $a,b,c$? What if there exist several such polynomials?  
> **username_0**: Yes finding $a,b,c,d$.  
> **username_0**: Finding one quadruple in $\Bbb Z_{\geq0}[x]$ suffices.  

---

## 0 answers

