مسئله صدق‌پذیری دودویی

صدق‌پذیری یا ارضاپذیری در دانش رایانه پرسمانی است که می‌پرسد آیا می‌توان ارزش متغیرهای فرمولی دودویی را به گونه‌ای یافت که فرمول درست باشد؟ بنابراین اگر چنین ارزش‌دهی پیدا شود، گوییم پرسمان صدق‌پذیر است. وگرنه، بی‌گمان این فرمول همواره نادرست است و گوییم که فرمول صدق‌ناپذیر است. برای نمونه، فرمول  صدق‌پذیر است چون اگر ارزش‌های  و  درست باشند، فرمول همواره درست است.
پرسمان صدق‌پذیری نخستین پرسمانی است که ان‌پی کامل بودنش نشان داده شده‌است. کوک و لوین نشان دادند الگوریتمی شناخته‌شده‌ای نیست که در زمانی کوتاه پرسمان صدق‌پذیری را حل کند. محدودهٔ وسیعی از بقیهٔ مسائل تصمیم‌گیری و بهینه‌سازی طبیعی می‌توانند به موارد مسئلهٔ صدق‌پذیری تبدیل شوند. یک رده از الگوریتم‌ها به نام حل‌کننده‌های SAT به‌طور کارآمد می‌توانند زیرمجموعه‌ای به اندازهٔ کافی بزرگ از موارد SAT را حل کنند تا در حوزه‌های مختلف عملی از جمله طراحی مدار و قضیهٔ اثبات اتوماتیک مفید باشند. وسیعتر کردن قابلیت‌های الگوریتم‌های حل‌کنندهٔ SAT یک حوزهٔ در حال پیشرفت است. هرچند هیچ‌کدام از روش‌های کنونی نمی‌توانند همه‌ی موارد مسئلهٔ صدق‌پذیری را به‌طور کارآمد حل کنند.

تعریف‌ها، واژگان و کاربردها

در نظریه پیچیدگی محاسباتی مسئلهٔ صدق‌پذیری یک مسئلهٔ تصمیم است که نمونهٔ آن یک عبارت بولی می‌باشد که فقط با AND، OR، NOT، متغیرها و پرانتز نوشته شده‌است. سؤال این است که: آیا می‌توان به متغیرها مقادیر "درست" و "نادرست" داد تا عبارت موردنظر همواره درست باشد؟ یک فرمول از منطق گزاره‌ای صدق‌پذیر است اگر به متغیرهای آن بتوان مقادیر منطقی داد تا فرمول همواره درست باشد. مسئلهٔ صدق‌پذیری دودویی یک ان‌پی کامل است. مسئلهٔ صدق‌پذیری گزاره‌ای (PSAT)، که مشخص می‌کند آیا یک فرمول گزاره‌ای صدق‌پذیر هست یا نه، مهم‌ترین مسئله در حوزه‌های مختلف علوم رایانه است؛ نظیر علوم نظری رایانه، الگوریتم‌ها، هوش مصنوعی، طراحی پردازنده، اتوماسیون طراحی الکترونیکی و تایید.
یک متغیر یا خود آن متغیر یا نقیضش است. به‌طور مثال x۱ یک متغیر مثبت و (not(x۲ یک متغیر منفی است.
یک عبارت فصل منطقی از متغیرهاست. به‌طور مثال (x۱ V not(x۲ یک عبارت است.
در بعضی حالت‌های مسئله صدق‌پذیری دودویی، نیاز است که فرمول عطف منطقی چند عبارت باشد. حالتی که صدق‌پذیری یک فرمول به شکل عطف معمولی را بررسی می‌کنیم که هر عبارت حداکثر دارای سه متغیر باشد، ان‌پی کامل است؛ این مسئله "۳SAT" یا "۳CNFSAT" یا "۳-صدق‌پذیری" نامیده می‌شود. حالتی که فرمول موردبررسی دارای عبارت‌هایی با حداکثر دو متغیر باشد، ان‌ال کامل است؛ این مسئله "۲SAT" نامیده می‌شود. حالتی که فرمول موردبررسی دارای عبارت‌های هورن (که حداکثر یک متغیر مثبت دارند.) باشد، پی کامل است؛ این مسئله صدق‌پذیری هورن نامیده می‌شود.
قضیه کوک لوین عنوان می‌کند که مسئله دودویی صدق‌پذیری یک ان‌پی کامل است، در واقع این اولین مسئله‌ایست که اثبات شده ان‌پی کامل است.

2-صدق‌پذیری

همچنین مسئلهٔ SAT آسان‌تر است اگر تعداد متغیرهای یک عبارت به 2 محدود شده باشد، که در این حالت مسئله 2SAT نامیده می‌شود. این مسئله نیز می‌تواند در زمان چندجمله‌ای حل شود و در واقع برای ردهٔ ان‌ال کامل است. به‌طور مشابه اگر تعداد متغیرهای هر عبارت را به 2 محدود کرده و اعمال AND را به XOR تغییر دهیم، نتیجه یک 2-صدق‌پذیری XOR است که یک مسئلهٔ کامل برای SL = L می‌باشد.
یکی از مهم‌ترین محدودیت‌های SAT، مسئلهٔ HORNSAT می‌باشد که فرمول، یک عطف از چند عبارت هورن باشد. این مسئله با الگوریتم ارضاپذیری هورن با زمان چندجمله‌ای قابل حل است، و در اصل پی-کامل می‌باشد. می‌تواند به صورت نسخه‌ای از ردهٔ پی برای مسئلهٔ صدق‌پذیری دودویی دیده شود.
در صورتی که رده‌های پیچیدگی پی و ان‌پی یکسان نباشند، برخلاف SAT هیچ‌کدام از این محدودیت‌ها ان‌پی کامل نیستند. این فرضیه که پی و ان‌پی یکسان نیستند هنوز اثبات نشده‌است.

صدق‌پذیری هورن

یک عبارت هورن است اگر حداکثر یک متغیر مثبت داشته باشد. این‌گونه عبارت‌ها مورد توجه هستند چون می‌توانند استلزام یک متغیر از مجموعه‌ای از متغیرها را بیان کنند. در واقع یک عبارت مانند  می‌تواند به شکل  بازنویسی شود، یعنی اگر  همه "درست" باشند، y هم باید "درست" باشد.
مسئلهٔ تصمیم‌گیری در مورد صدق‌پذیری عبارات هورن در پی (P) است. این مسئله نیز می‌تواند با یک مرحله از انتشار واحد حل شود که مدل کمینهٔ واحد از مجموعه‌ای از عبارات هورن ایجاد می‌کند.
یک تعمیم از ردهٔ فرمول‌های هورن، فرمول با قابلیت اسم‌گذاری دوبارهٔ هورن است که یک مجموعه از فرمول‌ها می‌باشد که با فرمت هورن می‌تواند با چند متغیر به همراه نقیض مربوطهٔ آن‌ها جایگزین شود. بررسی وجود این جایگزینی می‌تواند در زمان خطی انجام بگیرد؛ پس صدق‌پذیری همچین فرمولی در پی (P) است، چون می‌تواند اول با این جایگزینی و سپس بررسی صدق‌پذیری فرمول هورن نتیجه شده حل شود.

صدق‌پذیری XOR

یک حالت خاص دیگر مسائلی هستند که در آن‌ها هر عبارت فقط اعمال XOR را شامل می‌شود. چون عمل XOR معادل جمع در زمینهٔ گالویس از اندازهٔ 2 است، عبارات می‌توانند مانند یک دستگاه معادلات خطی دیده شوند و از روش‌های متناظر مانند حذف گاوسی می‌توان برای یافتن راه‌حل آن‌ها استفاده کرد.

قضیهٔ دوگانگی شافر

محدودیت‌های بالا (CNF، 2CNF، 3CNF، هورن) فرمول موردبررسی را به عطفی بودن زیرفرمول محدود می‌کنند؛ هر محدودیت یک شکل خاص برای همهٔ زیرفرمول‌ها مشخص می‌کند: به‌طور مثال، فقط عبارات دودویی می‌توانند یک زیرفرمول در 2CNF باشند.
قضیهٔ دوگانگی شافر عنوان می‌کند که برای هر محدودیتی بر اعمال بولی که می‌توانند این زیرفرمول‌ها را شکل دهند، مسئلهٔ صدق‌پذیری متناظر یک پی یا ان‌پی کامل است. عضویت در پی (P) برای صدق‌پذیری 2CNF و فرمول هورن، حالت‌های خاصی از این قضیه هستند.

رفتار در زمان اجرا

همانطور که در بالا به‌طور خلاصه بیان شد، هرچند که مسئله، ان‌پی کامل است، مثال‌های عملی زیادی می‌توانند خیلی زود حل شوند. اکثر مسائل عملی در حقیقت "آسان" هستند، پس حل‌کنندهٔ SAT به آسانی می‌تواند یک راه‌حل بیابد یا اثبات کند که وجود ندارد؛ با وجود آنکه آن مورد هزاران متغیر و ده‌ها هزار محدودیت دارد. بقیهٔ مسائل کوچک زمان‌های اجرایی را ارائه می‌دهند که به صورت نمایی باشند و به مرور غیرعملی شده‌اند. متأسفانه هیچ راه قابل اطمینانی وجود ندارد که سختی مسئله را بدون امتحان آن بیان کند. پس تقریباً همهٔ حل‌کننده‌های SAT شامل زمان‌های اضافه می‌شوند، پس با آنکه هیچ راه‌حلی نیافته‌اند اما به پایان خواهند رسید. در نهایت حل‌کننده‌های SAT مختلفی موارد مختلف آسان یا سخت را پیدا خواهند کرد و بعضی از آن‌ها در اثبات صدق‌ناپذیری و دیگران در یافتن راه‌حل برترند. همهٔ آن رفتارها در مسابقه‌های حل SAT دیده می‌شوند.

الگوریتم‌های حل‌کنندهٔ SAT

دو رده از الگوریتم‌های با کارایی بالا برای حل مسائل SAT وجود دارد: الگوریتم تضاد-راندهٔ شناختن عبارت، که می‌توان به عنوان نوعی دیگر از الگوریتم‌های DPLL به آن نگاه کرد، و همچنین الگوریتم‌های اتفاقی جستجوی محلی مانند WalkSAT.
یک حل‌کنندهٔ مسئلهٔ صدق‌پذیری DPLL، یک روند جستجوی بازگشتی اصولی را به کار می‌گیرد تا فاصلهٔ واگذاری متغیرها برای یافتن واگذاری صدق‌پذیر را کشف کند. در اوایل دههٔ 60 میلادی، روند اصلی جستجو در دو مقاله مطرح شد (منابع زیر را ببینید) و حال به عنوان الگوریتم دیویس-پاتنام-لاگمن-لاولند (یا به اختصار DPLL یا DLL) مشهور است. از لحاظ تئوری کران پایین نمایی برای خانوادهٔ الگوریتم‌های DPLL اثبات شده‌است.
حل‌کننده‌های SAT نوین (که در 10 سال گذشته ایجاد شدند) در دو نوع بیان می‌شوند: "تضاد-رانده" و "پیش‌بین". حل‌کننده‌های تضاد-رانده الگوریتم جستجوی DPLL اصلی را با تحلیل تضاد کارآمد، شناختن عبارت، بازگشت بدون ترتیب زمانی (الگوریتم پس‌پرش)، و همچنین انتشار واحد "دو-متغیر-تماشا"، انشعاب انطباقی و راه‌اندازی مجدد تصادفی، افزایش می‌دهند. نشان داده شده‌است که این "الحاقات" اصولی جستجو به صورت تجربی برای رسیدگی به موارد زیادی از SAT که در اتوماسیون طراحی الکترونیکی (EDA) به وجود می‌آیند ضروری هستند. حل‌کننده‌های پیش‌بین به خصوص کاهش‌ها (رفتن به ورای انتشار عبارت واحد) و کشف‌کننده‌ها را تشدید کردند و در کل در موارد پیچیده از حل‌کننده‌های تضاد-رانده قوی‌تر عمل می‌کنند.
حل‌کننده‌های SAT نوین تأثیرات مهمی بر زمینه‌های تأیید نرم‌افزاری، حل‌کردن محدودیت‌های هوش مصنوعی و تحقیق در عملیات دارند. حل‌کننده‌های قوی به آسانی به صورت نرم‌افزار آزاد و متن‌باز در دسترس هستند. به‌طور خاص نرم‌افزار تضاد-راندهٔ MiniSAT که در مسابقهٔ SAT در سال 2005 نسبتاً موفق بود، فقط دارای حدود 600 خط برنامه است. یک مثال از حل‌کننده‌های پیش‌بین march_dl است که در مسابقهٔ SAT در سال 2007 برنده شد.
انواع خاصی از موارد بزرگ تصادفی صدق‌پذیر از SAT با انتشار نظرسنجی (SP) قابل حل هستند. به خصوص در طراحی پردازنده و برنامه‌های تایید، صدق‌پذیری و دیگر خواص منطقی از فرمول گزاره‌ای داده‌شده بعضی اوقات بر پایهٔ نمایشی از فرمول در نمودار تصمیم‌گیری دودویی (BDD) تصمیم‌گیری می‌شوند.