Substitutions into propositional tautologies

DOI10.1016/J.IPL.2006.09.002zbMath1185.68629OpenAlexW2052661699MaRDI QIDQ845921

Jan Krajíček

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.09.002

zbMATH Keywords

computational complexityautomated theorem provingproof complexity

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Tautologies from Pseudo-Random Generators
• On the weak pigeonhole principle
• The relative efficiency of propositional proof systems
• Pseudorandom Generators in Propositional Proof Complexity
• Diagonalization in proof complexity
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Natural proofs

This page was built for publication: Substitutions into propositional tautologies