ACM通信

研究突出了

技术角度:从简单算法隐藏的模式

由Madhu苏丹
ACM通讯，2011年4月，54卷4号，107页
10.1145/1924421.1924445
评论

9021960864034418159813这个数字是随机的吗?有教养的人可能会说“不!”没有一根弦是随机的，”更轻蔑地说:“来吧!然而，在我有限的头脑中，这个字符串确实看起来是随机的。是否有一种方法可以使用一些正式的数学来证明我的naïveté?伪随机性的现代理论^2,5确实设法解释了这样的现象，弦似乎随机的头脑简单。这一理论认为，关键在于随机性真正取决于“旁观者”，或者更确切地说，取决于随机性测试者的计算能力。相对于复杂而强大的算法，更简单或资源有限的算法显得更随机。

我们为什么要关心?因为随机性是计算中的关键资源。蒙特卡洛模拟大量应用于预测计算。在理论方面，如果使用随机性，算法会得到极大的简化或加速。分布式计算中的基本任务(如同步)只能用随机性来解决。没有随机性，就没有希望保持隐私和保密。与此同时，我们在现实中处理的许多随机性都不是“纯粹的”。它们不是独立随机位的集合，而是由其他进程产生的。知道算法或计算过程如何在有些随机的字符串中工作成为一个反复出现的问题的本质。(例如，你真的应该相信由蒙特卡洛算法使用c++ rand程序中的随机性做出的核电安全计算吗?)

这类问题在伪随机性理论中形式化为:它考虑随机性的某些来源X(形式上由某个概率分布给出n-bit字符串)，以及一类布尔算法一个(决定布尔问题的算法)并询问某些算法是否存在一个所生成的随机字符串的访问方式非常不同X，比纯随机字符串的效果好吗?如果每一个算法一个的行为大致相同X我们说纯粹的随机性X是伪随机一个。在这个例子中，X= X可能是选择一个随机整数的源我在1至10000之间，并输出[我+ 1];…［我+ 20] where [j]表示j的第一个数字。给定一类算法一个有人可能会问，X看伪随机一个吗?

不幸的是，回答这样的问题会给计算理论带来根本性的挑战。证明X看起来随机一个涉及到没有算法一个可以检测的数字所表示的模式。证明某些类型的算法不能完成某些任务是理论计算机科学的一个主要挑战(最臭名昭著的问题是“是”P＝NP?”)。

考虑到分析字符串中看似随机性的主要障碍，对伪随机性的研究仍处于初级阶段也就不足为奇了。马克·布雷弗曼(Mark Braverman)的以下论文对这一领域进行了新的阐释。它说明了一大类源，只要它们有足够的局部随机性，就能骗过一大类但相对简单的计算“AC”的算法⁰功能。”交流⁰函数是那些其输入输出行为可以描述为一个布尔逻辑电路组成n任意扇入的输入导线和多项式多个非门、与门和或门。交流⁰在高度并行的机器上，对应于恒定时间内可计算任务的函数，是我们似乎确实了解的一类计算任务的前沿。例如,交流⁰函数可以计算两个的和n / 2-位整数，而不是它们的乘积(因此我们知道它们不能做的事情)。事实上，我们甚至知道一个相对小的熵的显式来源，在这门课上看起来是伪随机的。⁴然而，究竟是什么来源欺骗了这类算法，我们的理解是未知的，这领先于Linial和Nisan^3.推测某种形式的“局部随机性”对这类算法来说是足够随机的。他们指出的局部随机性被广泛称为“有限独立性”。一个源X据说是k-wise独立的，如果有的话k随机源的比特是完全随机和独立的。Linial和Nisan推测，对于每一个恒定深度的电路，一些(logn）^{O (1)}明智的独立看起来是纯粹的n随机性。二十多年来，这个猜想一直没有得到解决。直到最近,宝宝¹解决了猜想的一个特例(以AC为例)⁰函数对应深度2电路，或“DNF公式”)。

现在布雷弗曼的研究肯定地解决了这个猜想。在这个过程中，他揭示了AC⁰函数可以用低阶多元多项式来描述，展示布尔计算和更多经典数学之间的一些相互作用。我们需要看到更多这样的连接，才能希望解决计算复杂性的广泛挑战Pvs。NP)．事实上，甚至要解决开篇所暗示的问题“AC的伪随机数字是多少?⁰功能呢?," one needs to understand much more. Fortunately, Braverman's work may have reduced this question to a purely number-theoretic one: Are the digits of locally random?

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2011 ACM股份有限公司

---

没有发现记录