ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION

DOI10.1142/S0219061311000979zbMath1259.03073MaRDI QIDQ3094358

Jan Krajíček

Publication date: 24 October 2011

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

zbMATH Keywords

propositional logicdisjunction propertyproof complexityreflection principlepropositional proof systemNisan-Wigderson generator

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (5)

ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Circuit lower bounds in bounded arithmetics ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Unnamed Item

Cites Work

• Bounded arithmetic and the polynomial hierarchy
• Hardness vs randomness
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Tautologies from Pseudo-Random Generators
• On the weak pigeonhole principle
• Nisan-Wigderson generators in proof systems with forms of interpolation
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems
• Foundations of Cryptography
• Diagonalization in proof complexity
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• Computational Complexity
• Logical Foundations of Proof Complexity

This page was built for publication: ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION