Random resolution refutations

DOI10.4230/LIPICS.CCC.2017.1MaRDI QIDQ5111131zbMATH OpenFDO

Authors Pavel Pudlák, Neil Thapen

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2017.1

zbMATH Keywords

proof complexityrandom resolution

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Random resolution refutations
• Refuting random 3CNF formulas in propositional logic
• scientific article; zbMATH DE number 1775444
• Lower bounds for k-DNF resolution on random 3-CNFs
• Random CNF's are hard for the polynomial calculus

Cited in

(6)

• Random resolution refutations
• A feasible interpolation for random resolution
• Many hard examples for resolution
• Lower bounds for k-DNF resolution on random 3-CNFs
• Verifying Refutations with Extended Resolution
• Resolution lower bounds for refutation statements

This page was built for publication: Random resolution refutations

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