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.