On the complexity of choosing the branching literal in DPLL

DOI10.1016/S0004-3702(99)00097-1zbMath0939.68646OpenAlexW2057832617MaRDI QIDQ1978252

Paolo Liberatore

Publication date: 4 June 2000

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(99)00097-1

zbMATH Keywords

complexitypropositional satisfiabilityDavis-Putnam

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the limit of branching rules for hard random unsatisfiable 3-SAT, New updating criteria for conflict-based branching heuristics in DPLL algorithms for satisfiability, How important are branching decisions: fooling MIP solvers, On the relation among answer set solvers, Argumentation in artificial intelligence

Cites Work

• How good are branching rules in DPLL?
• Solving propositional satisfiability problems
• Branching rules for satisfiability
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Unnamed Item
• Unnamed Item
• Unnamed Item