Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-124 | 1st May 2016 20:04

Noncommutative Valiant's Classes: Structure and Complete Problems

RSS-Feed




Revision #1
Authors: Vikraman Arvind, Pushkar Joglekar, Raja S
Accepted on: 1st May 2016 20:04
Downloads: 857
Keywords: 


Abstract:


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).



Changes to previous version:

(1) $\mathrm{VNP_{nc}}$-intermediate problem section is modified.
(2) There are some modifications in other sections also.


Paper:

TR15-124 | 3rd August 2015 13:57

Noncommutative Valiant's Classes: Structure and Complete Problems





TR15-124
Authors: Vikraman Arvind, Pushkar Joglekar, Raja S
Publication: 3rd August 2015 15:03
Downloads: 1502
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint