Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NON-COMMUTATIVE POLYNOMIAL:
Reports tagged with non-commutative polynomial:
TR11-088 | 7th June 2011
Pavel Hrubes

#### How much commutativity is needed to prove polynomial identities?

Let $f$ be a non-commutative polynomial such that $f=0$ if we assume that the variables in $f$ commute. Let $Q(f)$ be the smallest $k$ such that there exist polynomials $g_1,g_1', g_2, g_2',\dots, g_k, g_k'$ with $f\in I([g_1,g_1'], [g_2, g_2'],\dots, [g_k, g_k'] )\,,$
where $[g,h]=gh-hg$. Then $Q(f)\leq {n\choose 2}$, where ... more >>>

ISSN 1433-8092 | Imprint