Conditional lower bounds for failed literals and related techniques

DOI10.1007/978-3-319-09284-3_7MaRDI QIDQ3192056zbMATH OpenOpenAlexFDO

Authors Matti Järvisalo, Janne H. Korhonen

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_7

Mathematics Subject Classification ID

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

• Efficient CNF simplification based on binary implication graphs
• Improving resolution width lower bounds for k-CNFs with applications to the strong exponential time hypothesis
• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
• Alternation-trading proofs, linear programming, and lower bounds
• Hard satisfiable instances for DPLL-type algorithms

Cited in

(1)

• Efficient CNF simplification based on binary implication graphs

This page was built for publication: Conditional lower bounds for failed literals and related techniques

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