Noncommutative Valiant's Classes: Structure and Complete Problems

摘要

In this paper we explore the noncommutative analogues, VP nc and VNP nc , of Valiant's algebraic complexity classes and show some striking connections to classical formal language theory. Our main results are the following:(1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for the class VNP nc under abp reductions. Likewise, it turns out that PAL (Palindrome polynomials defined from palindromes) are complete for the class VSKE W nc (defined by polynomial-size skew circuits) under abp reductions. The proof of these results is by suitably adapting the classical Chomsky-Sch"{u}tzenberger theorem showing that Dyck languages are the hardest CFLs.(2) Next, we consider the class VNP nc . It is known~cite{HWY10a} that, assuming the sum-of-squares conjecture, the noncommutative polynomial w x 0 x 1 n w w requires exponential size circuits. We unconditionally show that w x 0 x 1 n w w is not VNP nc -complete under the projection reducibility. As a consequence, assuming the sum-of-squares conjecture, we exhibit a strictly infinite hierarchy of p-families under projections inside VNP nc (analogous to Ladner's theorem~cite{Ladner75}). In the final section we discuss some new VNP nc -complete problems under abp -reductions.(3) Inside VNP nc too we show there is a strict hierarchy of p-families (based on the nesting depth of Dyck polynomials) under the abp reducibility.