2015/08/03 by V. Arvind, Pushkar S. Joglekar, Pushkar S Joglekar +4
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Coding theory and cryptography #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1508.00395
arxiv created 2015/08/03 · arxiv updated 2015/08/04
In this paper we explore the noncommutative analogues, VPnc and VNPnc, 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 VPnc under ≤abp reductions. Likewise, it turns out that PAL (Palindrome polynomials defined from palindromes) are complete for the class VSKEWnc (defined by polynomial-size skew circuits) under ≤abp reductions. The proof of these results is by suitably adapting the classical Chomsky-Schützenberger theorem showing that Dyck languages are the hardest CFLs. (2) Next, we consider the class VNPnc. It is known~\citeHWY10a that, assuming the sum-of-squares conjecture, the noncommutative polynomial ∑_w∈\x0,x1\nww requires exponential size circuits. We unconditionally show that ∑_w∈\x0,x1\nww is not VNPnc-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 VNPnc (analogous to Ladner's theorem~\citeLadner75). In the final section we discuss some new VNPnc-complete problems under ≤abp-reductions. (3) Inside VPnc too we show there is a strict hierarchy of p-families (based on the nesting depth of Dyck polynomials) under the ≤abp reducibility.