Tautologies from Pseudo-Random Generators
Tautologies from Pseudo-Random Generators
复制标题
来自伪随机生成器的同义反复
DOI：
--
复制
发表时间：
2001
影响因子：
0.6
通讯作者：
J. Krajícek
中科院分区：
文献类型：
--
作者：
J. Krajícek
摘要我们考虑由Krajíček[11]和Alekhnovich等人定义的伪随机数生成器形成的重言式。[2]。我们通过Krajíček[11]提出的关于有界算术的一个猜想，解释了证明扩展Frege系统的难度的一种策略。此外，我们还给出了一个与猜想等价的纯有限陈述，其形式为施加于函数的硬度条件。
Abstract We consider tautologies formed from a pseudo-random number generator, defined in Krajíček [11] and in Alekhnovich et al. [2]. We explain a strategy of proving their hardness for Extended Frege systems via a conjecture about bounded arithmetic formulated in Krajíček [11]. Further we give a purely finitary statement, in the form of a hardness condition imposed on a function, equivalent to the conjecture.