Pseudorandomness and complexity

伪随机性和复杂性

• 批准号: 298363-2007
• 负责人: Kabanets, Valentine
• 金额: $ 2.11万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2011
• 资助国家: 加拿大
• 起止时间: 2011-01-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=480707
• 关键词: Pseudorandomness; complexity

Randomness has become an indispensable tool in many areas of computer science: algorithm design, networking, error-correcting codes, cryptography, etc. While the use of randomness is unavoidable for certain applications (e.g., cryptographic constructions), other applications can be made completely deterministic. One of the main challenges of theoretical computer science is to understand the exact power of randomness in computation. In particular, it is a big open question whether every randomized polynomial-time algorithm has an equivalent deterministic polynomial-time algorithm (i.e., can be efficiently derandomized). Answering this question is important for algorithm design, as fast deterministic algorithms are usually preferable to randomized ones. On the other hand, there is a deep connection between trying to derandomize probabilistic algorithms and trying to prove lower bounds on the computational power of Boolean circuits. The latter problem has been actively researched for several decades with the goal of resolving the "P vs. NP" question. However, no strong circuit lower bo unds are known for any explicit Boolean function.

随机性已经成为计算机科学的许多领域中不可或缺的工具：算法设计、网络、纠错码、密码学等。密码构造），其他应用可以完全确定。理论计算机科学的主要挑战之一是理解计算中随机性的确切力量。特别地，是否每个随机化多项式时间算法都具有等效的确定性多项式时间算法（即，可以有效地去随机化）。考虑这个问题对算法设计很重要，因为快速确定性算法通常比随机算法更好。另一方面，试图去随机化概率算法和试图证明布尔电路计算能力的下限之间有着深刻的联系。几十年来，人们一直在积极研究后一个问题，目标是解决“P与NP”问题。然而，没有强电路下界已知的任何显式布尔函数。