Comparing notions of full derandomization
Comparing notions of full derandomization
复制标题
比较完全去随机化的概念
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
L. Fortnow
中科院分区：
文献类型：
--
作者：
L. Fortnow
大多数完全去随机化的假设分为两组等价的陈述：那些等价于有效的伪随机发生器的存在和那些等价于近似电路的接受概率。我们给出了第一个相对化的世界，其中这些等价陈述的集合彼此不等价。
Most of the hypotheses of full derandomization fall into two sets of equivalent statements: those equivalent to the existence of efficient pseudorandom generators and those equivalent to approximating the accepting probability of a circuit. We give the first relativized world where these sets of equivalent statements are not equivalent to each other.