اثبات np کامل بودن مساله sat¶

تعریف مساله ها¶

در این قسمت چند مساله از خانواده مسائل sat را می بینیم که در ادامه به آن ها اشاره خواهیم کرد. کلمه sat مخفف satisfiablity به معنای توانایی برآورده کردن شرایط است. هر مساله یک مساله تصمیم است که ما باید در آن الگوریتمی ارائه کنیم که بررسی کند آیا می توان خروجی ها را به گونه ای قرار داد تا ورودی یک شود یا خیر.

circuit-sat: در این مساله یک مدار منطقی ورودی می گیریم که از گیت های اور و اند و نات تشکیل شده است. این مدار تعدادی ورودی و دقیقا یک خروجی دارد. الگوریتم باید تشخیص دهد که آیا ممکن است ورودی ها را به گونه ای تنظیم کرد که خروجی برابر یک شود؟ توجه کنید که مدار هایی که این مساله به عنوان ورودی می گیرد، یک مدار منطقی ترکیبی است یعنی دوری وجود ندارد و خروجی یک گیت روی ورودی های آن تاثیر نمی گذارند.

sat: این مساله حالت خاصی از مساله بالا است که در آن خروجی به یک گیت اند بزرگ متصل است و هر پایه از گیت اند، به یک گیت اور بزرگ وصل است که هر پایه از آن، یا به خود ورودی وصل است و یا به نقیض ورودی. به عبارت دیگر، یک عبارت به صورت \((x_1 \lor x_7 \lor \overline{x_3}) \land ... \land (x_2 \lor \overline{x_1} \lor ... \lor x_7)\) به شما داده می شود و شما باید تعیین کنید که آیا می توان متغیر ها را با اعداد 0 و 1 جایگزین کرد به طوری که نتیجه عبارت (علامت شبیه هفت به معنای یای منطقی، علامت هشت به معنای و منطقی و خط روی متغیر به معنای نقیض منطقی است) برابر یک شود.

‪3-sat‬: این مساله حالت خاصی از مساله بالا است که در آن، هر پرانتز دقیقا ۳ متغیر دارد. به طور مشابه، ‪2-sat‬ تعریف می شود که در فصل های دیگر با الگوریتم حل آن آشنا می شوید.

اثبات np کامل بودن circuit-sat¶

یک مساله np دلخواه را در نظر بگیرید. این مساله، یک تایید کننده در زمان چند جمله ای دارد. هر تایید کننده، خود یک مساله تصمیم است. نکته کلیدی این است که هر الگوریتم تصمیم که زمان اجرای چند جمله ای داشته باشد را می توان به یک مدار منطقی ترکیبی تبدیل کرد. اگرچه اثبات دقیق این مطلب، نیاز به شناخت دقیق تری از الگوریتم دارد و مناسب این کتاب نیست، اما می توانید آن را روی مسائل کنار دستتان امتحان کنید. مثلا یک مدار برای تایید کننده مساله دور همیلتونی یا مساله عدد رنگی ارائه کنید.

پس تصمیم کننده را به ازای ورودی با طول ثابت، به یک مدار منطقی ترکیبی تبدیل می کنیم که تعداد گیت هایش برحسب ورودی، چند جمله ای باشد. حال اگر بتوان به تایید کننده ورودی داد که آن را تایید کند، می توان به مدار معادل آن نیز ورودی داد تا خروجی اش یک شود. بنابراین جواب مساله اصلی، معادل با نتیجه circuit-sat روی این مدار است. پس هر مساله در کلاس np را می توان به مساله circuit-sat در زمان چند جمله ای کاهش داد و بنابراین مساله circuit-sat یک مساله np کامل است.

کاهش مساله circuit-sat به sat¶

در این قسمت ثابت خواهیم کرد که مساله ‪3-sat‬ نیز یک مساله np کامل است و از آن نتیجه می شود که حالت کلی تر مساله، یعنی مساله sat نیز np کامل است. ابتدا توجه کنید که دقیقا سه متغیره بودن جملات، اهمیت چندانی ندارد زیرا می توان جملات را با اضافه کردن متغیر های تکراری بزرگ کرد، مثلا \((x \lor \overline{y})\) را به \((x \lor \overline{y} \lor \overline{y})\) تبدیل کرد.

حال یک مدار ترکیبی را در نظر بگیرید. ابتدا تمام گیت های اند یا اور که بیشتر از دو ورودی دارند را تبدیل به گیت های دو ورودی کنید. با این کار طول ورودی به صورت خطی زیاد می شود که اهمیتی برای ما ندارد. حال به ازای هر دسته از نقاط هم پتانسیل (یعنی نقاطی که با سیم به هم متصل هستند) یک متغیر در نظر می گیریم. حالا به ازای هر گیت، چند شرط اضافه می کنیم به طوری که رفتار گیت را تضمین کند. یعنی شرط ها تنها در صورتی برقرار باشند که خروجی گیت متناظر با ورودی های گیت و تابع گیت باشد. برای مثال فرض کنید \(a\) و \(b\) ورودی های یک گیت اند و \(x\) خروجی آن باشد. با اضافه کردن شرط های \(\overline{a} \lor \overline{b} \lor x\) و \(a \lor \overline{x}\) و \(b \lor \overline{x}\) می توانیم تضمین کنیم که مقدار \(x\) حتما برابر و منطقی \(a\) و \(b\) باشد. به همین ترتیب می توان برای گیت اور و گیت نات نیز چنین شرط هایی تعریف کرد. با اند گرفتن از این شرط ها و خروجی مدار که خود یک متغیر است، می توان یک ورودی برای 3-sat ساخت که حواب داشتنش معادل جواب داشتن همان مدار در circuit-sat است. پس این مساله و حالت کلی آن یعنی sat هر دو np کامل هستند.