Pseudorandomness and complexity

伪随机性和复杂性

• 批准号: 298363-2007
• 负责人: Kabanets, Valentine
• 金额: $ 2.11万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=456846
• 关键词: 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 vs. NP”问题。然而，对于任何显式布尔函数，没有已知的强电路下限。