Randomness and Non-determinism
Randomness and Non-determinism
复制标题
随机性和非确定性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
L. Levin
中科院分区：
文献类型：
--
作者：
L. Levin
指数化使得这条线的位大小与已知宇宙中粒子的数量（<< 2^{300}）之间存在差异。在60年代，指数时间算法从计算机理论中被驱逐，打破了它与数学逻辑的脐带。它在确定性计算和它以前不起眼的工具--随机性和非确定性之间创造了一个很深的鸿沟。在过去的几十年里，我们对这两种基本的计算“自由”的力量知之甚少，但它们之间的关系正在出现一些模糊的模式。在这一领域，类似的技术模式对截然不同的结果起着重要作用，这似乎更有趣。像多线性和低次多元多项式，低周期群上的傅里叶变换这样的思想似乎很有启发性。这次谈话调查了最近的一些结果。其中之一，在一个更强的形式比以前公布的，下面描述。
Exponentiation makes the difference between the bit-size of this line and the number (<< 2^{300}) of particles in the known Universe. The expulsion of exponential time algorithms from Computer Theory in the 60's broke its umbilical cord from Mathematical Logic. It created a deep gap between deterministic computation and -- formerly its unremarkable tools -- randomness and non-determinism. Little did we learn in the past decades about the power of either of these two basic "freedoms" of computation, but some vague pattern is emerging in relationships between them. The pattern of similar techniques instrumental for quite different results in this area seems even more interesting. Ideas like multilinear and low-degree multivariate polynomials, Fourier transformation over low-periodic groups seem very illuminating. The talk surveyed some recent results. One of them, given in a stronger form than previously published, is described below.