Hierarchies, Circuit Lower Bounds and Pseudorandomness

点击翻译按钮获取中文摘要

Computational complexity theory studies the possibilities and limits of efficient computation. The central question in this area is the P vs NP question, which asks if every computational problem solvable in non-deterministic polynomial time (NP) is also solvable in deterministic polynomial time (P). Solvability in P typically indicates feasibility in the real world.The NP vs P question is critical because several important problems, such as Boolean satisfiability, Integer Linear programming and Clique, are known to be in NP but not known to be efficiently solvable. The Clay Mathematics Institute has listed the NP vs P question among its seven ``Millennium Problems'' and offered 1,000,000 dollars for its solution - an indication of its centrality not just in computer science but also in mathematics. The question is also relevant to several other fields such as economics, biology and physics, because there are important problems in these fields as well which are known to be in NP but not known to be in P.It is widely believed that NP does not equal P, however it seems dauntingly hard to give a formal proof of this. A large part of the reason for this is the fundamental distinction between upper bounds and lower bounds on computational complexity. Proving that a problem is in (deterministic) polynomial time can be done just by giving an algorithm that runs in polynomial time and solves the problem. However, proving that a problem is not in polynomial time requires showing that every polynomial time algorithm fails to solve the problem. This is considerably harder because polynomial time is a relatively rich model of computation - it seems hard to isolate structural features which problems solvable in polynomial time have in common. The NP vs P question seems out of reach of current techniques, however there are other lower bounds questions which are more accessible such as the hierarchies question and the fixed polynomial circuit lower bounds question. These have natural motivations of their own - the hierarchies question asks whether more problems can be solved given more of a given resource, say probabilistic time, while the circuit lower bounds question asks if a problem can be solved efficiently in hardware. These questions are closely connected to each other, as well as to the question of derandomizing probabilistic algorithms. Many algorithms used in practice assume access to an independent and unbiased source of random bits. However, it's unclear whether true randomness exists in the real world. Thus it is of interest to minimize the randomness requirements of algorithms. The theory of pseudo-randomness addressed precisely this question - to what extent can randomness requirements of algorithms be minimized? This is particularly relevant to cryptography and security, since any cryptographic protocol must use randomness to be secure, and using imperfect randomness may make a protocol insecure.We propose to study hierarchies, circuit lower bounds and derandomization questions in this project, as well as the connections between them. Our goal is to prove new lower bounds, and in the process of doing so to formulate new lower techniques which could have other applications, perhaps ultimately even to the NP vs P question. We have also formulated two new directions for research on these fundamental problems, which connect to finite model theory and proof complexity. The hope is that perspectives and insights from these other areas might complement established ideas to achieve progress on these important and difficult problems.