Short propositional refutations for dense random 3CNF formulas

DOI10.1016/j.apal.2014.08.001zbMath1391.03042MaRDI QIDQ741088

D. Kharzeev

Publication date: 10 September 2014

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2014.08.001

zbMATH Keywords

propositional proof complexity; Frege proofs; threshold logic; random 3-SAT; refutation algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

03F30: First-order arithmetic and fragments

03B05: Classical propositional logic

03F20: Complexity of proofs