权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Hierarchies, Circuit Lower Bounds and Pseudorandomness

层次结构、电路下界和伪随机性

基本信息

批准号：
EP/H05068X/1
负责人：
Rahul Santhanam
金额：
$ 12.78万
依托单位：
University of Edinburgh
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2010
资助国家：
英国
起止时间：
2010 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FH05068X%2F1
关键词：
Hierarchies Circuit Lower Bounds 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.

计算复杂性理论研究有效计算的可能性和限制。这一领域的核心问题是P vs NP问题，它询问是否每个可在非确定性多项式时间（NP）中解决的计算问题也可在确定性多项式时间（P）中解决。P中的可解性通常表明在真实的世界中的可行性。NP与P问题是关键的，因为几个重要的问题，如布尔可满足性，线性规划和团，是已知的NP，但不知道是有效的可解的。克莱数学研究所（Clay Mathematics Institute）将NP vs P问题列为其七个“千年难题”之一，并悬赏100万美元寻求解决方案--这表明它不仅在计算机科学中，而且在数学中都处于中心地位。这个问题也与其他几个领域有关，如经济学、生物学和物理学，因为这些领域也有一些重要的问题，已知属于NP，但不知道属于P。其中很大一部分原因是计算复杂性的上限和下限之间的根本区别。证明一个问题是在（确定性的）多项式时间内可以通过给出一个在多项式时间内运行并解决问题的算法来完成。然而，要证明一个问题不是多项式时间的，需要证明每个多项式时间算法都不能解决这个问题。这是相当困难的，因为多项式时间是一个相对丰富的计算模型-似乎很难孤立的结构特征，在多项式时间解决的问题有共同之处。NP vs P问题似乎超出了当前技术的范围，但是还有其他更容易获得的下界问题，例如层次结构问题和固定多项式电路下界问题。这些问题有其自身的自然动机-层次结构问题询问是否可以在给定资源的情况下解决更多的问题，比如概率时间，而电路下限问题询问是否可以在硬件中有效地解决问题。这些问题彼此密切相关，以及去随机化概率算法的问题。在实践中使用的许多算法假设访问一个独立的和公正的随机位源。然而，在真实的世界中是否存在真正的随机性还不清楚。因此，最小化算法的随机性要求是有意义的。伪随机性理论正好解决了这个问题--算法的随机性要求能最小化到什么程度？这与密码学和安全性特别相关，因为任何密码协议都必须使用随机性才能安全，而使用不完全随机性可能会使协议变得不安全，我们建议在这个项目中研究层次结构，电路下界和去随机化问题，以及它们之间的联系。我们的目标是证明新的下界，并在此过程中制定新的较低的技术，可以有其他的应用，也许最终甚至NP与P的问题。我们还制定了两个新的方向，研究这些基本问题，连接到有限模型理论和证明的复杂性。希望这些其他领域的观点和见解可以补充既定的想法，以便在这些重要和困难的问题上取得进展。