A proof complexity generator

MaRDI QIDQ4630802zbMATHFDO

Authors Jan Krajíček

Publication date 23 April 2019

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)

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

Cited in

(5)

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

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)