Refuting random 3CNF formulas in propositional logic

MaRDI QIDQ2939527zbMATH OpenFDO

Authors

Publication date 22 January 2015

zbMATH Keywords

\(\mathrm{TC}^0\)-Frege proofsrandom 3CNF formulasrandom 3CNF refutation

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of proofs (03F20)

Recommendations

• Short propositional refutations for dense random 3CNF formulas
• Short propositional refutations for dense random 3CNF formulas
• scientific article; zbMATH DE number 5899254
• scientific article; zbMATH DE number 1775444
• Sparser random 3-SAT refutation algorithms and the interpolation problem (extended abstract)

Cited in

(9)

• Short propositional refutations for dense random 3CNF formulas
• scientific article; zbMATH DE number 5899254 (Why is no real title available?)
• Some 3CNF properties are hard to test
• Lower bounds for k-DNF resolution on random 3-CNFs
• Random resolution refutations
• Sparser random 3-SAT refutation algorithms and the interpolation problem (extended abstract)
• Automata, Languages and Programming
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Short propositional refutations for dense random 3CNF formulas

This page was built for publication: Refuting random 3CNF formulas in propositional logic

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