Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-040 | 10th March 2010 20:03

Relationless completeness and separations


Authors: Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
Publication: 10th March 2010 20:15
Downloads: 3759


This paper extends Valiant's work on $\vp$ and $\vnp$ to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds.
We define analogs of Valiant's classes $\vp$ and $\vnp$, as well as of the polynomials permanent and determinant, in these worlds.
We then prove that even in a completely relationless world which assumes no commutativity nor associativity,
permanent remains $\vnp$-complete,
and determinant can polynomially simulate any arithmetic formula, just as in the standard commutative, associative world of Valiant.

In the absence of associativity, the completeness proof gives rise to the following combinatorial problem: what is the smallest binary tree which contains as minors {\em all} binary trees with $n$ leaves. We give an explicit construction of such a universal tree of polynomial size, a result of possibly independent interest.

Given that such non-trivial reductions are possible even without commutativity and associativity, we turn to lower bounds. In the non-associative, commutative world we prove exponential circuit lower bounds on explicit polynomials, separating the non-associative commutative analogs of $\vp$ and $\vnp$.
Obtaining such lower bounds and a separation in the complementary associative, non-commutative world has been open for about 30 years.

ISSN 1433-8092 | Imprint