Exponential bounds for DPLL below the satisfiability threshold

MaRDI QIDQ5501251zbMATH OpenFDO

Authors

Publication date 3 August 2015

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Automata, Languages and Programming
• The efficiency of resolution and Davis-Putnam procedures
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

Cited in

(12)

• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• Dismantlability, connectedness, and mixing in relational structures
• Limitations of restricted branching in clause learning
• Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
• Lower bounds for myopic DPLL algorithms with a cut heuristic
• scientific article; zbMATH DE number 1445296 (Why is no real title available?)
• Dismantlability, Connectedness, and Mixing in Relational Structures
• Walksat Stalls Well Below Satisfiability
• Automata, Languages and Programming
• Gap preserving reductions between reconfiguration problems
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

This page was built for publication: Exponential bounds for DPLL below the satisfiability threshold

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