Meanders, Ramsey theory and lower bounds for branching programs
Meanders, Ramsey theory and lower bounds for branching programs
复制标题
曲折、拉姆齐理论和分支程序的下界
DOI：
10.1109/sfcs.1986.31
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
W. Maass
中科院分区：
文献类型：
--
作者：
N. Alon;W. Maass
提出了一种求解一般输入无关序列计算模型中某些函数的时空复杂度下界的新方法。这可以通过研究以下集合等式问题SE（n,m）的内在复杂性来证明：给定一个序列x1，x2,...., xn, y1,……，yn（每2n个m位）决定集合[x1，....，xn]和[y1，…], yn)一致。我们证明了对于任意log log n≤m≤1/2log n且任意1≤s≤log n，任意输入无关顺序计算用2m/s空间求解SE（n,m）需要Ω(n ？s)时间。这个结果对于n，m，s的所有允许值都是明显的，并且是已知的第一个在这种一般计算模型上的集合识别问题的非平凡时间空间权衡下界（对于空间= ω (log n)）。我们的方法还提供了几个自然对称函数的任意分支程序（不一定是输入无关的）长度的下界，改进了钱德拉、富斯特和利普顿、Pudlák和Ajtai等人的结果。例如，我们表明，对于多数函数，任何宽度为w(n)的分支程序的长度为ω(n ？Log n/w (n) ？log w (n))，特别是对于有界宽度，我们得到长度ω (n log n)（独立于我们的工作Babai等人[BPRS]同时证明了最后一个结果）。分支程序的下界意味着为相同的计算问题生成任意计算图所需的步数的下界。为了建立下界，我们引入了捕捉序列超集中型性质的曲流的新概念。我们通过一个新的拉姆齐理论引理证明了弯曲长度的下界，这个引理本身就很有趣。这个引理还有其他的应用，包括深度为2的弱超集中物大小的紧下界，它加强了已知的Pippenger [Pi]的下界。拉姆齐理论在下界论证中的这些应用的一个令人惊讶的新特征是，没有数字需要特别大，并且所得到的几个超线性下界实际上是最优的。
A novel technique for obtaining lower bounds for the time versus space complexity of certain functions in a general input oblivious sequential model of computation is developed. This is demonstrated by studying the intrinsic complexity of the following set equality problem SE(n,m): Given a sequence x1,x2,....,xn, y1,....,yn of 2n numbers of m bits each, decide whether the sets [x1,....,xn] and [y1,...,yn] coincide. We show that for any log log n ≤ m ≤1/2log n and any 1 ≤ s ≤ log n, any input oblivious sequential computation that solves SE(n,m) using 2m/s space, takes Ω(n ? s) time. This result is sharp for all admissible values of n,m,s and is the first known nontrivial time space tradeoff lower bound (for space = ω (log n) of a set recognition problem on such a general model of computation. Our method also supplies lower bounds on the length of arbitrary (not necessarily input oblivious) branching programs for several natural symmetric functions, improving results of Chandra, Furst and Lipton, of Pudlák and of Ajtai et. al. For example we show that for the majority - function any branching program of width w(n) has length ω(n ? log n/w (n) ? log w (n)), in particular for bounded width we get length ω (n log n) (independently of our work Babai et. al. [BPRS] have simultaneously proved this last result). Our lower bounds for branching programs imply lower bounds on the number of steps that are needed to pebble arbitrary computation graphs for the same computational problems. To establish our lower bounds we introduce the new concept of a meander that captures superconcentrator-type properties of sequences. We prove lower bounds on the length of meanders via a new Ramsey theoretic lemma that is of interest in its own right. This lemma has other applications, including a tight lower bound on the size of weak superconcentrators of depth 2 that strengthens the known lower bound of Pippenger [Pi]. A surprising new feature of these applications of Ramsey theory in lower bound arguments is the fact that no numbers are required to be unusually large and that several of the resulting superlinear lower bounds are in fact optimal.