Overview
Davis-Putnam Algorithm is a sat solving method for satisfiability. It works by eliminating variables by resolution before checking the remaining formula.
ExtendedSource checked
Davis-Putnam Algorithm
Davis-Putnam Algorithm addresses satisfiability by eliminating variables by resolution before checking the remaining formula.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- SAT Solving
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
satisfiabilitysat solvingoptimization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(2^n)
Worst
O(2^n)
Space
O(2^n)
When to Use
- Use Davis-Putnam Algorithm when solving satisfiability and you want to benefit from eliminating variables by resolution before checking the remaining formula.
- Choose it when O(2^n) average/worst-case time and O(2^n) memory match your workload profile.
- Prefer it over DPLL or CDCL when the problem structure favors satisfiability.
When Not to Use
- Avoid when exact optimality is required but the method is heuristic or approximate.
- Avoid when constraints are poorly defined or cheap feasibility checks are unavailable.
What It Does
- Computes satisfiability within SAT Solving workloads (O(2^n) time, O(2^n) space).
- Works by eliminating variables by resolution before checking the remaining formula.
- Maintains key invariants across satisfiability, sat solving, optimization.
Use Cases
- Production and research workloads requiring satisfiability via eliminating variables by resolution before checking the remaining formula.
- SAT Solving pipelines where O(2^n) time and O(2^n) space fit system constraints.
- Engineering comparisons against DPLL and CDCL when tuning satisfiability.
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Pseudocode
- 1.Formulate the satisfiability instance, objective function, and initial candidate state or active search tree.
- 2.Evaluate candidate feasibility and objective bounds (satisfiability, sat solving).
- 3.Advance the search by eliminating variables by resolution before checking the remaining formula.
- 4.Prune suboptimal branches, propagate unit/conflict clauses, or update incumbent best solutions.
- 5.Return the optimal or best-found feasible assignment once convergence or exhaustion is reached.
Canonical Example
- Input
- Objective, constraints, and candidate variables configured for a representative satisfiability test case
- Output
- Best known feasible solution satisfying Davis-Putnam Algorithm invariants
- Explanation
- Davis-Putnam Algorithm processes the input by eliminating variables by resolution before checking the remaining formula, tracking satisfiability and sat solving to produce the verified satisfiability result.
Implementation Notes
- State the objective and feasibility checks in code before adding pruning.
- Keep incumbent solutions separate from bounds.
- Add tests for infeasible and exactly-tied cases.
Common Pitfalls
- Assuming a heuristic is exact without checking its guarantee.
- Using weak bounds that make search behave like brute force.
- Forgetting infeasible, empty, or degenerate constraint cases.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow eliminating variables by resolution before checking the remaining formula on a small satisfiability example.
Step 1 of 5: Formulate the satisfiability instance, objective function, and initial candidate state or active search tree.
optimization-mechanismNotes
Davis-Putnam Algorithm operates in O(2^n) time and O(2^n) space within the SAT Solving family. Often compared with DPLL and CDCL.
Sources (2)
What each reference supports for this entry.
Handbook of Satisfiability
BookReference for Davis-Putnam Algorithm within SAT solving, including search, simplification, learning, or local-search mechanisms.
Open sourceDavis-Putnam 1960
PaperOriginal Davis-Putnam reference for resolution-based satisfiability and quantification procedures.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toCDCL
Optimization · Core
Davis-Putnam Algorithm and CDCL are practical alternatives within satisfiability, with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toDPLL
Davis-Putnam Algorithm and DPLL are practical alternatives within satisfiability, with different assumptions and tradeoffs.
Alternative toCDCL
Davis-Putnam Algorithm and CDCL are practical alternatives within satisfiability, with different assumptions and tradeoffs.
Alternative toWalkSAT
Davis-Putnam Algorithm and WalkSAT are practical alternatives within satisfiability, with different assumptions and tradeoffs.
Related Algorithms
Tags
OptimizationConstraint Solving