ECCC-Report TR10-040https://eccc.weizmann.ac.il/report/2010/040Comments and Revisions published for TR10-040en-usWed, 10 Mar 2010 20:15:11 +0200
Paper TR10-040
| Relationless completeness and separations |
Pavel Hrubes,
Avi Wigderson,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2010/040This 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.Wed, 10 Mar 2010 20:15:11 +0200https://eccc.weizmann.ac.il/report/2010/040