A non-linear time lower bound for Boolean branching programs
A non-linear time lower bound for Boolean branching programs
复制标题
布尔分支程序的非线性时间下界
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
M. Ajtai
中科院分区：
文献类型：
--
作者：
M. Ajtai
我们证明，对于所有正整数k，对于所有足够小的/spl epsiv/> 0，如果n足够大，则没有大小小于2/sup em/的布尔（或2路）分支程序，用于所有输入x/sps sube/{0，1，...，n-1}在时间kn中计算与属性x/spl的所有对（x，y）集合（x，y）的元素的奇偶元isin/x，y/spl isin/x，x <y，x+y/spl isin/x。为了证明这一事实，我们表明，如果a =（/spl alpha // sub i，j/）/sub i = 0，j = 0 // sup n/是n矩阵随机n，则是n矩阵，带有2条件是“/spl forall/，j，k，l/l/spl isin/{0，1，...，n-1}，i+j = k+l Ingus/spl alpha // sub I，sub I，sub i， J/=/SPL alpha // sub k，l/“然后，A a的级别/spl delta/n的级别/spl delta/n spl delta/n subsatrix至少为c/spl delta/| log/| log/spl delta/|/sup- 2/n，其中c> 0是绝对常数，相对于/spl delta/，n足够大。
We prove that for all positive integer k and for all sufficiently small /spl epsiv/>0 if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2/sup em/ which for all inputs X/spl sube/{0, 1, ..., n-1} computes in time kn the parity of the number of elements of the set of all pairs (x,y) with the property x/spl isin/X, y/spl isin/X, x<y, x+y/spl isin/X. For the proof of this fact we show that if A=(/spl alpha//sub i,j/)/sub i=0, j=0//sup n/ is a random n by n matrix over the field with 2 elements with the condition that "/spl forall/, j, k, l/spl isin/{0, 1, ..., n-1}, i+j=k+l implies /spl alpha//sub i,j/=/spl alpha//sub k,l/" then with a high probability the rank of each /spl delta/n by /spl delta/n submatrix of A is at least c/spl delta/|log /spl delta/|/sup -2/n, where c>0 is an absolute constant and n is sufficiently large with respect to /spl delta/.