Lower bounds and derandomizations for branching programs

一般信息： 我的研究计划的长期目标是帮助阐明有效可解问题的复杂性类P的结构。具体地说，P中的每个问题都能用对数内存量解决吗？这个问题早在P与NP问题之前就出现了，并暗示了复杂性理论的主要缺陷：尽管一代研究人员进行了大量的努力，但对于复杂性类NP中的问题的复杂性，还没有真正令人满意的下界，更不用说P类了。 具体内容： 在接下来的5年里，我将重返分支程序的研究，这是一种已知的捕获内存资源的计算模型。我首先建议集中精力解释为什么在NP中没有比二次型更好的分支程序大小下界。为解决问题而获得计算资源下限的障碍以前已经被发现。拉兹博罗夫和鲁迪奇在1997年提出了这样一种障碍的一个有影响力的概念：通过他们所称的“自然证明”获得了强大的下界，以排除被称为有效伪随机数生成器的物体的存在，人们普遍认为这种物体是存在的。因此，我们当前的许多最好的复杂性下界都是通过自然证明获得的经验事实，在上面的意义上是一个障碍。 在过去的25年里，在内存受限计算的背景下，已经有很多关于伪随机性的研究。我希望从这项工作中得出结论，以便针对分支程序的立方体大小下限定义等价的自然证明，并得出不太可能的去随机化结果。我将探索自然证明的可能变体，涉及最近引入的伪确定性计算的概念。我将在代数自动机理论的指导下研究有界宽度分支程序的去随机化问题。我将考虑受限分支程序的概率变体(如单调或增量)，并分析它们的表现力和去随机性。 重要意义： 严格证明计算复杂性下限可能非常有用。一个著名的例子出现在密码学中，目前缺乏计算难度证明，无法排除聪明的个人或组织可能侵入被认为是安全的通信渠道的可能性。其他例子来自一个30年前的发现，现在得到了广泛的利用：如果某些计算问题被证明是困难的，那么构建伪随机数生成器的工具就会随之而来；这些工具反过来可以用来将已知的高效概率算法转换为同样有效的确定性算法(从而摆脱了依赖随机位带来的不确定性)。寻找障碍来证明下限，也可以提出改进现有算法的新方法。

GENERAL: The long-term goal of my research program is to help elucidating the structure of the complexity class P of efficiently solvable problems. In particular, can every problem in P be solved using a logarithmic amount of memory? This question predates the P versus NP question and hints at the main shortcoming of complexity theory: despite intensive efforts by a generation of researchers, no truly satisfactory lower bounds on the complexity of problems within the complexity class NP, let alone the class P, are known. SPECIFICS: In the next 5 years I will return to the study of branching programs, a computation model known to capture the memory resource. I first propose to concentrate on trying to explain why no branching program size lower bound better than quadratic is known for problems in NP. Obstacles to obtaining lower bounds on computational resources for solving a problem have been identified before. One influential notion of such an obstacle was developed by Razborov and Rudich in 1997: strong lower bounds obtained by means of what these authors named "natural proofs" were shown to rule out the existence of objects called efficient pseudorandom number generators, widely believed to exist. The empirical fact that many of our best current complexity lower bounds were obtained by natural proofs is thus an obstacle in the above sense. The last 25 years have seen much research on pseudo-randomness in the context of memory-bounded computation. I am hoping to draw from this work in order to define the equivalent of natural proofs against (say) cubic size lower bounds for branching programs and to derive unlikely derandomization consequences. I will explore possible variants of natural proofs involving the recently introduced notion of pseudo-deterministic computation. I will investigate derandomization of bounded-width branching programs under the guidance of algebraic automata theory. I will consider probabilistic variants of restricted branching programs (such as monotone or incremental) and analyse their expressivity and their derandomizations. SIGNIFICANCE: Rigorously proving computational complexity lower bounds can be very useful. A famous example arises in cryptography, where the current lack of computational hardness proofs prevents ruling out that a clever individual or organization might break into communication channels thought to be secure. Other examples follow from a 30-year-old discovery by now exploited extensively: if certain computational problems could be proved hard, then tools to construct pseudorandom number generators would follow; such tools in turn could serve to transform known efficient probabilistic algorithms into equally efficient deterministic (hence freed from the uncertainty that accompanies the reliance on random bits) algorithms. Searching for obstacles to proving lower bounds could as well suggest new ways to improve existing algorithms.