The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question continues to remain open, we make some progress towards its resolution. To that effect, we generalise the notion of ordered polynomials in the non-commutative setting (defined by \Hrubes, Wigderson and Yehudayoff (2011)) to define abecedarian polynomials and models that naturally compute them. Our main contribution is a possible new approach towards separating formulas and ABPs in the non-commutative setting, via lower bounds against abecedarian formulas. In particular, we show the following. There is an explicit n-variate degree d abecedarian polynomial $f_{n,d}(x)$ such that 1. $f_{n, d}(x)$ can be computed by an abecedarian ABP of size O(nd); 2. any abecedarian formula computing $f_{n, \log n}(x)$ must have size that is super-polynomial in n. We also show that a super-polynomial lower bound against abecedarian formulas for $f_{\log n, n}(x)$ would separate the powers of formulas and ABPs in the non-commutative setting.
翻译:这项工作的动机问题是一个长期存在的未决问题,由Nisan(1991年)提出,涉及代数分支程序(ABPs)和公式在非混合环境中的相对权力。尽管一般问题仍然未解决,但我们在解决方面取得了一些进展。为此,我们在非混合环境中(由\Hrubes、Wigderson和Yehudayoff (2011年)定义了残疾多语种和自然计算它们的模型)中,将定购多语种的概念普遍化。我们的主要贡献是在非混合环境中将公式和公式分开的一种可能的新做法,通过对低端偏颇公式的下限,我们特别展示了以下内容。在非混合环境中(由\Hrubes、Wigdererson 和Yehudayoff (2011年)定义了一个明确的正态程度,即1. 美元、 dx(x) 美元、 dx(x) 美元和美元(x)可以由大小的低端的ABP(n) ; 2. 任何非正态公式的确定一个以美元计面的超级货币规模。