کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419359 683793 2013 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Semidefinite resolution and exactness of semidefinite relaxations for satisfiability
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Semidefinite resolution and exactness of semidefinite relaxations for satisfiability
چکیده انگلیسی

This paper explores new connections between the satisfiability problem and semidefinite programming. We show how the process of resolution in satisfiability is equivalent to a linear transformation between the feasible sets of the relevant semidefinite programming problems. We call this transformation semidefinite programming resolution, and we demonstrate the potential of this novel concept by using it to obtain a direct proof of the exactness of the semidefinite formulation of satisfiability without applying Lasserre’s general theory for semidefinite relaxations of 0/1 problems. In particular, our proof explicitly shows how the exactness of the semidefinite formulation for any satisfiability formula can be interpreted as the implicit application of a finite sequence of resolution steps to verify whether the empty clause can be derived from the given formula.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issue 18, December 2013, Pages 2812–2826
نویسندگان
, ,