Noncommutative Valiant's classes: structure and complete problems

DOI10.1145/2956230MaRDI QIDQ4973866zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 6 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.00395

algebraic branching programs noncommutative algebraic complexity classes noncommutative arithmetic circuits projection reductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Abstract: In this paper we explore the noncommutative analogues,

m a t h r m {V P}_{n c}

and

m a t h r m {V N P}_{n c}

, 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

m a t h r m {V P}_{n c}

under

l e_{a b p}

reductions. Likewise, it turns out that

m a t h r m P A L

(Palindrome polynomials defined from palindromes) are complete for the class

m a t h r m {V S K E W}_{n c}

(defined by polynomial-size skew circuits) under

l e_{a b p}

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

m a t h r m {V N P}_{n c}

. It is known~cite{HWY10a} that, assuming the sum-of-squares conjecture, the noncommutative polynomial

s u m_{w i n {x_{0}, x_{1}}^{n}} w w

requires exponential size circuits. We unconditionally show that

s u m_{w i n {x_{0}, x_{1}}^{n}} w w

is not

m a t h r m {V N P}_{n c}

-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

m a t h r m {V N P}_{n c}

(analogous to Ladner's theorem~cite{Ladner75}). In the final section we discuss some new

m a t h r m {V N P}_{n c}

-complete problems under

l e_{a b p}

-reductions. (3) Inside

m a t h r m {V P}_{n c}

too we show there is a strict hierarchy of p-families (based on the nesting depth of Dyck polynomials) under the

l e_{a b p}

reducibility.

Recommendations

Cited in

(1)

scientific article; zbMATH DE number 7250152 (Why is no real title available?)

This page was built for publication: Noncommutative Valiant's classes: structure and complete problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973866)