satisfiability problem

An Explicit Semidefinite Characterization of Satisfiability for Tseitin Instances

  • Miguel F. Anjos
    • Categories 0-1 Programming, Basic Sciences Applications, Semi-definite Programming Tags , , , ,

    This paper is concerned with the application of semidefinite programming to the satisfiability problem, and in particular with using semidefinite liftings to efficiently obtain proofs of unsatisfiability. We focus on the Tseitin satisfiability instances which are known to be hard for many proof systems. We present an explicit semidefinite programming problem with dimension linear in … Read more

    On Semidefinite Programming Relaxations for the Satisfiability Problem

  • Miguel F. Anjos
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper is concerned with the analysis and comparison of semidefinite programming (SDP) relaxations for the satisfiability (SAT) problem. Our presentation is focussed on the special case of 3-SAT, but the ideas presented can in principle be extended to any instance of SAT specified by a set of boolean variables and a propositional formula in … Read more