论文部分内容阅读
作为计算复杂性的一个重要分支，判定树复杂性从上世纪70年代开始就受到了广泛的关注，并且被发现和其他的理论计算机方向，比如通信复杂性，电路复杂性，布尔函数分析等有着深刻的联系。考察不同的判定树复杂性度量之间的关系，以及为特定的问题设计高效的判定树算法并证明其最优性是判定树复杂性中的两个核心课题。本文中，围绕以下四个重要问题展开研究。 1，敏感度猜想:作为判定树复杂性领域最重要最具挑战性的问题之一，敏感度猜想自1994年由Noam Nisan和Mario Szegedy[1]提出后就受到了相当多的关注，它断言判定树复杂性的两个度量——敏感度和块敏感度——是多项式相关的。尽管人们对此进行了大量的研究，距离证明这个猜想仍然是遥远的。本文中，通过利用超立方体上的一个等周不等式以及复杂细致的分析，得到了目前已知的块敏感度和敏感度之间最好的关系。 2，k一致超图性质的敏感度:一张n个点的k一致超图可以用一个(nk)长的01串来表示，所以一个图的集合就对应一个布尔函数，说这个函数是超图性质，如果同构的图具有相同的函数值。由此，就可以利用判定树复杂性中的工具去研究超图的结构，比如人们发现判定树复杂性中的敏感度可以很好的刻画随机超图的相变程度[2-4]。Laszlo Babai猜想[5]任意的k一致超图性质的敏感度都至少是Ω(nk/2)，这里n是超图的顶点数。本文中，构造了一系列敏感度为O(n[k/3])的k一致超图性质，从而证否了Babai的猜想。另外，还证明了一个k一致超图性质敏感度的下界，从而在这类特殊的函数上验证了敏感度猜想。 3，不同环内布尔函数的多项式度之间的关系:布尔函数在不同环内的多项式表示在计算机科学的很多领域都是一个非常有用的工具，比如机器学习[6-9]，计算复杂性[1,10-16]，显式的组合构造[7-20]等等。这里的一个核心课题是去考察这些多项式的度之间的关系，特别地，Parikshit Gopalan等人[21]询问一个布尔函数在实数域中的多项式的度和环Z/mZ中的多项式的度是不是多项式相关的，这里m是一个包含至少两个素数因子的整数。围绕这个开放问题，我们的结果包括:首先，在证实这个开放问题的方向上，给出一些非平凡的等价猜想，从而降低了证实原问题的难度，并且在一些特殊函数，比如k一致超图性质以及转折数比较小的函数上证实了这个问题;然后，在证否这个开放问题的方向上，给出了两者之间一个平方量级的差距;最后，证明了一个相关的计算复杂性的定理，从计算复杂性的角度揭示了为什么这个问题难以被解决。 4，基于比较的最优归并排序算法:归并排序问题是最重要以及最基本的算法问题之一:给定两个排好序的数组A和B，在最坏情况下利用尽量少的比较次数把A和B合并为一个有序数组。容易看到，归并排序算法可以用判定树来表示。本文中，考察一类最常见的归并排序算法——纸带归并算法——的最优范围。本文首先证明了当两个数组的长度比不超过1.52倍时，纸带归并算法是最优的，这是40年来对Yao等人[22-24]的结果的首次改进，然后，证明了仅仅利用刚才的方法是不可能把1.52倍提高到1.8倍的。最后，在2|A|-2≤|B|≤3|A|范围内，改进了目前已知最好的算法。特别的，证明了当|B|≥2|A|-2时，纸带归并算法肯定不是最优的。