Lower bounds and derandomizations for branching programs

GENERAL:******我的研究计划的长期目标是帮助阐明有效可解问题的复杂性类P的结构。特别是，P中的每个问题都可以使用对数内存量来解决吗？这个问题早于P对NP问题，并暗示了复杂性理论的主要缺点：尽管一代研究人员进行了密集的努力，但在复杂性类NP中没有真正令人满意的问题复杂性下界，更不用说P类了。****** details:******在接下来的5年中，我将回到分支程序的研究，这是一种已知的捕获内存资源的计算模型。我首先建议集中精力解释为什么在NP问题中没有比二次型更好的分支程序大小下界。为了解决一个问题，获得计算资源下界的障碍以前已经被识别出来。1997年，Razborov和Rudich提出了这种障碍的一个有影响力的概念：通过这些作者称为“自然证明”的方法获得的强下界被证明可以排除被称为有效伪随机数生成器的对象的存在，这种对象被广泛认为存在。因此，在上述意义上，我们目前许多最好的复杂性下界都是通过自然证明获得的经验事实是一个障碍。******在过去的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.********