A two-phase algorithm for solving a class of hard satisfiability problems

DOI10.1016/S0167-6377(98)00052-2zbMath0960.90100MaRDI QIDQ1306378

Hans van Maaren, Joost P. Warners

Publication date: 20 May 2001

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmsatisfiabilityDavis-Putnam algorithm

Mathematics Subject Classification ID

Mathematical programming (90C99)

Related Items (10)

The state of SAT ⋮ Filter-based resolution principle for lattice-valued propositional logic LP\((X)\) ⋮ Unnamed Item ⋮ How to fake an RSA signature by encoding modular root finding as a SAT problem ⋮ Equivalent literal propagation in the DLL procedure ⋮ Recognition of tractable satisfiability problems through balanced polynomial representations ⋮ Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions ⋮ An improved semidefinite programming relaxation for the satisfiability problem ⋮ Non-clausal redundancy properties ⋮ Equivalency reasoning to solve a class of hard SAT problems.

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Recognition of tractable satisfiability problems through balanced polynomial representations
• The complexity of satisfiability problems
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• The complexity of theorem-proving procedures
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: A two-phase algorithm for solving a class of hard satisfiability problems