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”问题。但是，没有任何明确的布尔函数闻名强的电路下BO UND。