Time-space trade-off lower bounds for randomized computation of decision problems
Time-space trade-off lower bounds for randomized computation of decision problems
复制标题
决策问题随机计算的时空权衡下界
DOI：
10.1145/636865.636867
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Erik Vee
中科院分区：
文献类型：
--
作者：
P. Beame;M. Saks;Xiaodong Sun;Erik Vee
我们证明，即使允许计算有少量输入的误差，我们的界限的随机计算也是第一个时间空间的折衷。由Ajtai和Beame，Jayram和Saks使用的，我们的结果也对先前的结果进行了定量改进。决策问题可以自然地分为具有boolean域的功能的结果，也就是说，每个输入变量均为{0,1} - 值，而大域的情况则为</i>，如果每个输入变量从大小随变量数量增长的集合的值。在布尔域的情况下，ajtai公开了明确的函数类别，并证明了任何确定性的布尔分支程序或使用SPACE的任何确定性布尔分支程序或RAM <i> s </i> = <i> o </i>（<i> n </i>）需要超级线性时间<i> t </i>来计算它们的功能形式。没有在他的论文中给出，而是优化参数中的参数给出<i> t </i> =ω（<i> n n log log log <i> n </i>/log log log log log <i> n </i>）对于<i> s </i> = <i> o </i>（<i> n </i> <sup> 1-＆epsis; </sup>）。由Ajtai考虑，我们证明了一个时间空间表格的权衡（对于带错误的随机分支程序） log（<i> n/s </i>）。这样可以将下限的按时改进到ω（<i> n </i>＆sqrt; log <i> n </i>/log log log <i> n </i>）。在大域中，我们证明表格的下限<i> t </i> = ω（<i> n </i>＆sqrt; log（<i> n/s </i>）/log log（<i> n/s </i>））用于随机计算元素独特性函数和形式的下限<i> t <i> =ω（<i> n </i> log（<i> n/s </i>））用于随机计算Ajtai的锤击量紧密问题和某些功能在大型田地上与二次形式相关联。
We prove the first time-space lower bound trade-offs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques are extension of those used by Ajtai and by Beame, Jayram, and Saks that applied to deterministic branching programs. Our results also give a quantitative improvement over the previous results.Previous time-space trade-off results for decision problems can be divided naturally into results for functions with <i>Boolean domain</i>, that is, each input variable is {0,1}-valued, and the case of <i>large domain</i>, where each input variable takes on values from a set whose size grows with the number of variables.In the case of Boolean domain, Ajtai exhibited an explicit class of functions, and proved that any deterministic Boolean branching program or RAM using space <i>S</i> = <i>o</i>(<i>n</i>) requires superlinear time <i>T</i> to compute them. The functional form of the superlinear bound is not given in his paper, but optimizing the parameters in his arguments gives <i>T</i> = Ω(<i>n</i> log log <i>n</i>/log log log <i>n</i>) for <i>S</i> = <i>O</i>(<i>n</i><sup>1−&epsis;</sup>). For the same functions considered by Ajtai, we prove a time-space trade-off (for randomized branching programs with error) of the form <i>T</i> = Ω(<i>n</i> &sqrt; log(<i>n/S</i>)/log log (<i>n/S</i>)). In particular, for space <i>O</i>(<i>n</i><sup>1−&epsis;</sup>), this improves the lower bound on time to Ω(<i>n</i>&sqrt; log <i>n</i>/log log <i>n</i>).In the large domain case, we prove lower bounds of the form <i>T</i> = Ω(<i>n</i>&sqrt; log(<i>n/S</i>)/log log (<i>n/S</i>)) for randomized computation of the element distinctness function and lower bounds of the form <i>T</i> = Ω(<i>n</i> log (<i>n/S</i>)) for randomized computation of Ajtai's Hamming closeness problem and of certain functions associated with quadratic forms over large fields.