文章基本信息

标题：Tautologies from pseudo-random generators
本地全文：下载
作者：Jan Krajicek
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider tautologies formed from a pseudo-random number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99} and in Alekhnovich et.al. \cite{ABRW}. We explain a strategy of proving their hardness for EF via a conjecture about bounded arithmetic formulated in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a purely finitary statement, in a form of a hardness condition posed on a function, equivalent to the conjecture. This is accompanied by a brief explanation, aimed at non-logicians, of the relation between propositional proof complexity and bounded arithmetic.
关键词：arithmetic PV, Extended Frege proof system, Pseudo-Random Generators