In this paper we explore the noncommutative analogues, \mathrm{VP_{nc}} and
\mathrm{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 \mathrm{VP_{nc}} under
\le_{abp} reductions. To the best of our knowledge, these are the first
natural polynomial families shown to be
\mathrm{VP_{nc}}-complete. Likewise, it turns out that \mathrm{PAL} (Palindrome
polynomials defined from palindromes) are complete for the class
\mathrm{VSKEW_{nc}} (defined by polynomial-size skew circuits) under \le_{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) Assuming \mathrm{VP_{nc}} \neq \mathrm{VNP_{nc}}, we exhibit a strictly infinite
hierarchy of p-families, with respect to the projection
reducibility, between the complexity classes \mathrm{VP_{nc}} and \mathrm{VNP_{nc}}
(analogous to Ladner's theorem [Ladner75]).
(3) Inside \mathrm{VP_{nc}} too we show there is a strict hierarchy of
p-families (based on the nesting depth of Dyck polynomials) with
respect to the \le_{abp}-reducibility (defined explicitly in this
paper).
(1) \mathrm{VNP_{nc}}-intermediate problem section is modified.
(2) There are some modifications in other sections also.
In this paper we explore the noncommutative analogues, \mathrm{VP}_{nc} and
\mathrm{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 \mathrm{VNP}_{nc} under \le_{abp} reductions. Likewise, it turns out that \mathrm{PAL} (Palindrome
polynomials defined from palindromes) are complete for the class
\mathrm{VSKEW}_{nc} (defined by polynomial-size skew circuits) under \le_{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 \mathrm{VNP}_{nc}. It is known~\cite{HWY10a}
that, assuming the sum-of-squares conjecture, the noncommutative
polynomial \sum_{w\in\{x_0,x_1\}^n}ww requires exponential size
circuits. We unconditionally show that \sum_{w\in\{x_0,x_1\}^n}ww
is not \mathrm{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
\mathrm{VNP}_{nc} (analogous to Ladner's theorem~\cite{Ladner75}). In the
final section we discuss some new \mathrm{VNP}_{nc}-complete problems under
\le_{abp}-reductions.
(3) Inside \mathrm{VNP}_{nc} too we show there is a strict hierarchy of
p-families (based on the nesting depth of Dyck polynomials) under
the \le_{abp} reducibility.