Revision #1 Authors: Vikraman Arvind, Pushkar Joglekar, Raja S

Accepted on: 1st May 2016 20:04

Downloads: 806

Keywords:

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.

TR15-124 Authors: Vikraman Arvind, Pushkar Joglekar, Raja S

Publication: 3rd August 2015 15:03

Downloads: 1457

Keywords:

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.