A proof complexity generator

zbMATH Open1419.03052MaRDI QIDQ4630802FDOQ4630802

Authors: Jan Krajíček 

Publication date: 23 April 2019

Recommendations

• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Pseudorandom Generators in Propositional Proof Complexity
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• Diagonalization in proof complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (5)

• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• Towards NP-P via proof complexity and search
• Complexity of generation
• Pseudorandom Generators in Propositional Proof Complexity
• ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS

This page was built for publication: A proof complexity generator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4630802)