To print higher-resolution math symbols, click the
Hi-Res Fonts for Printing button on the jsMath control panel.

jsMath
Loading jsMath...
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: 1011
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: 1646
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