Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables with $x_i$ being non-commutative.

What is the complexity class and circuit and formula complexity of computing $\mathsf{Tr}(M^d)$ when $d=O(m)$ and $n=O(m^2)$?

Can this class be algebraic class $\mathsf{VNP}$?

  • $\begingroup$ Did you mean $\mathsf{VNP}_{nc}$ (the non-commutative version of $\mathsf{VNP}$)? Since you are computing noncommutative polynomials... Note that computing noncommutative determinant is hard (#P-hard in characteristic zero, $\mathsf{Mod_p P}$-hard in characteristic $p$), which should be roughly the same as your question. $\endgroup$ Apr 5 '16 at 15:50
  • $\begingroup$ @JoshuaGrochow I am sorry what if the non-commutative elements have matrix repressentation? $\endgroup$
    – user34945
    Apr 7 '16 at 1:06
  • $\begingroup$ You mean the $x_i$ are themselves matrices? $\endgroup$ Apr 7 '16 at 10:17
  • $\begingroup$ @JoshuaGrochow hmmm... yes in general many non-commutative structures have matrix representation. $\endgroup$
    – user34945
    Apr 7 '16 at 17:44

Your Answer

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