Pseudorandomness and complexity

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

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.