|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
18 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Noncommutative Valiant's Classes: Structure and Complete Problems | | V. Arvind
; Pushkar S Joglekar
; S. Raja
; | | Date: |
3 Aug 2015 | | 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. 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_{win{x_0,x_1}^n}ww$ requires exponential size circuits. We
unconditionally show that $sum_{win{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{VP}_{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. | | Source: | arXiv, 1508.0395 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER