文章基本信息

标题：On the proof complexity of the Nisan-Wigderson generator based on a hard NPcoNP function
本地全文：下载
作者：Jan Krajicek
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let g be a map defined as the Nisan-Wigderson generator but based on an NPcoNP -function f. Any string b outside the range of g determines a propositional tautology (g)b expressing this fact. Razborov \cite{Raz03} has conjectured that if f is hard on average for P/poly then these tautologies have no polynomial size proofs in the Extended Frege system EF. We consider a more general Statement (S) that the tautologies have no polynomial size proofs in any propositional proof system. This is equivalent to the statement that the complement of the range of g contains no infinite NP set. We prove that Statement (S) is consistent with Cook' s theory PV and, in fact, with the true universal theory \tpv in the language of PV. If PV in this consistency statement could be extended to "a bit" stronger theory (properly included in Buss's theory S21) then Razborov's conjecture would follow, and if it \tpv could be added too then Statement (S) would follow. We discuss this problem in some detail, pointing out a certain form of reflection principle for propositional logic, and we introduce a related feasible disjunction property of proof systems.
关键词：Nisan-Wigderson generator, Proof Complexity, Razborov