Long proofs of (seemingly) simple formulas

DOI10.1007/978-3-319-09284-3_10MaRDI QIDQ3192059zbMATH OpenOpenAlexFDO

Authors Mladen Mikša, Jakob Nordstrom

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-09284-3_10

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Finding the hardest formulas for resolution
• Locality and hard SAT-instances
• On tackling the limits of resolution in SAT solving
• Simple but hard mixed Horn formulas
• A note on SAT algorithms and proof complexity

Cited in

(5)

• Another look at degree lower bounds for polynomial calculus
• Locality and hard SAT-instances
• Finding the hardest formulas for resolution
• MaxSAT Resolution and Subcube Sums
• A generalized method for proving polynomial calculus degree lower bounds

Describes a project that uses

Uses Software

• Chaff

This page was built for publication: Long proofs of (seemingly) simple formulas

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